Home Page
Home Page
Archive > Posts > Tags > Math
Home
Projects
Archive
Forums
Contact
Misc
Site Map
Search:

Archives
Posts Updates
2006200720082009201020112012201320142015201620172018201920202021
202220232024Tags
By Viewed Sorted Scattered
By Used Sorted Scattered


See “Site Map” for Title lists


Date: 01/19/20 05:11am
The math behind the RSA encryption algorithm

I’ve always thought that the RSA and Diffie–Hellman public key encryption algorithm systems are beautiful in their complex simplicity. While there are countless articles out there explaining how to implement them, I have never really found one that I think describes the math behind then in a simple way, so I thought I’d give a crack at it.

Both algorithms are derived from 3 math axioms:
  1. This is called Modular exponentiation (hereby referred to as modexp). In the following, x is a prime numbers and p is an integer less than x.
    1. p^(x  ) mod x = p (e.x. 12^(17  ) mod 17 = 12)
    2. p^(x-1) mod x = 1 (e.x. 12^(17-1) mod 17 = 1 )
  2. A further derivation from the above formulas shows that we can combine primes and they work in the same manner. In the following, x and y are prime numbers and p is an integer less than x*y.
    1. p^((x-1)*(y-1)  ) mod (x*y) = 1 (e.x. 12^((13-1)*(17-1)  ) mod (13*17) = 1 )
      Note: This formula is not used in RSA but it helps demonstrate how the formulas from part 1 becomes formula 2b.
      Due to how modexp works with primes, values of p that are multiples of x or y do not work with 2a. 
    2. p^((x-1)*(y-1)+1) mod (x*y) = p (e.x. 12^((13-1)*(17-1)+1) mod (13*17) = 12)
  3. The final axiom is how modexp can be split apart the same way as in algebra where (x^a)^b === x^(a*b). For any integers p, x, y, and m: 
    (p^(x*y) mod m) === ((p^x mod m)^y mod m)

With these 3 axioms we have everything we need to explain how RSA works. To execute an RSA exchange, encrypted from Bob and decrypted by Alice, the following things are needed.

The variable Variable name Who has it Who uses it Description
Prime Numbers 1 and 2 Prime1, Prime2 Alice Alice Alice will use these to derive variables PubKey, PrivKey, and Modulo. In our examples we use small numbers, but in reality, very large primes will be used, generally of at least 256 bit size.
Public key PubKey Alice, Bob Bob Alice sends this to Bob so he can encrypt data to her. Bob uses it as an exponent in a modexp.
Private key PrivKey Alice Alice Alice uses this to decrypt what Bob sends her. Alice uses it as an exponent in a modexp.
Modulo Modulo Bob, Alice Bob, Alice Alice sends this to Bob. They both use it as a modulo in a modexp
Payload Data Payload The data bob starts with and turns into EncryptedPayload. Alice derives Payload back from EncryptedPayload

Now, let’s start with axiom 2b: 
Payload^((Prime1-1)*(Prime2-1)+1) mod (Prime1*Prime2) = Payload

Let’s change this up so the exponent is just 2 multiplications so we can use axiom 3 on it. We need to find 2 integers to become PubKey and PrivKey such that: 
PubKey*PrivKey=(Prime1-1)*(Prime2-1)+1

And Modulo is Prime1*Prime2.
So we now have: 
Payload^(PubKey*PrivKey) mod Modulo = Payload

Now, using axiom 3, we can turn it into this: 
(Payload^PubKey mod Modulo)^PrivKey mod Modulo = Payload

Now, we can split this up into:
Bob calculates and sends to Alice: Payload^PubKey mod Modulo=EncryptedPayload
Alice uses the received EncryptedPayload and performs: EncryptedPayload^PrivKey mod Modulo = Payload

And the process is complete!


However, there is 1 caveat that I didn’t cover which makes the encryption that what we currently have weak. The calculation of PubKey and PrivKey from Prime1 and Prime2 needs to follow some rather specific complex rules to make the keys strong. Without this, an attacker may be able to figure out Prime1 and Prime2 from the Modulo and PubKey, and could then easily derive PrivKey from it. I generally see the PubKey as 65535, or another power of 2 minus 1.



Date: 02/01/14 06:14pm
Math Facts Generator v1.0
Ultimately, programming is here to help other people make things easier
I created this simple little math facts worksheet generator for my kid to help her with learning her addition/subtraction/multiplication/division facts. I didn’t worry about creating an official project page for it since it is so simple.
v1.0, v1.0 Code, Current Version

Math Facts Example:
Math Facts Example

Print Preview Example:
Math Facts Print Preview Example

Date: 07/15/08 03:30am
Malcolm in the Middle - Mental Math
Because math is amazing...

This is a clip from the TV show “Malcolm in the Middle” in which the protagonist, Malcolm, demonstrates his freakish numeric abilities for the Krelboyne [the advanced learning/gifted class] Circus to save the day (episode “Krelboyne Picnic” Season 1 Episode 8).

I encoded this video, apparently, in February of 2007 and do not recall why. It’s a fun little clip, so instead of deleting it, since I recall that I could not find it at the time for whatever reason, I figured I’d put it here.


[flv 14.5MB] [Original avi 18.7MB]

Date: 01/02/08 07:51am
Pointless Math
Highway Hypnosis Boredom

So I just now made the ~200 mile drive from Austin (my current residence) to Dallas (where I grew up), both Texas of course, to take care of some stuff.  I’ll be driving back tonight, wee.  I have to say, that particular drive is one of the dullest in existence.  It’s not particularly long, traffic is normal, and nothing special per say, there’s just nothing to look at the whole way, And large gaps of road with no stops in between.  At least in the desert or middle states you have a little variety or mountains hopefully to look at.  I’ve made 24+ hour straight trips back and forth from Canada that I’ve loathed less :-).

Anywho, whenever I’m on a car trip of more than 100 miles, my mind always turns to counting down miles and running simple arithmetic in my head to calculate how much longer it will take at my current speed to reach my destination, how much time I can cut off if I went faster, etc.  This time around my mind turned towards deriving some formulas.  This is not the first time this has happened either XD.  I have to occupy myself with something when there’s just music to listen to and nothing else to do!  Driving is basically a muscle reflex for me on these long drives.


So there are 2 formulas that are useful for this situation.
#1 How much faster you are traveling per minute at different speeds.
#2 How much time you will save at different speeds.

Variables:
H=Higher Speed In MPH
L=Lower Speed In MPH
M=Number of miles to travel
The following are basic proofs of how the formulas work.  God... I swore after I got out of geometry I’d never think about proofs again.
The first one is very simple.
Number of extra miles traveled per hour = (H-L)
Number of extra miles traveled per minute = (H-L) mph / 60 minutes
So, for example, if you increase your speed from 20 to 30, you are going 10 miles an hour faster, which is 1/6 of a mile a minute.
The second one is slightly more difficult but much more useful.
h = Time it takes in hours to travel M at H = M miles / H mph
l = Time it takes in hours to travel M at L = M miles / L mph
Difference of time it takes between 2 speeds in hours = h-l
(M/H)-(M/L) [Substituting variables]
(MH-ML)/(HL) [Getting a common denominator]
M*(H-L)/(HL) [Distributive property]
So we can see that time saved, in hours, per mile is (H-L)/(H*L).  Just multiply that by M to get total time saved in hours.
With this second formula, we can see that in the higher speeds you go, the difference between the two speeds increase geometrically to get the same type of time savings (because H*L is a divisor, making it inversely proportional).
For example:
If H=20 mph and L=10mph
Time saved = (20-10)/(20*10) = 10/200 = 1/20 of an hour saved per mile, or 3 minutes
If H=30 mph and L=20mph
Time saved = (30-20)/(30*20) = 10/600 = 1/60 of an hour saved per mile, or 1 minute
If you wanted to save 3 minutes per mile when starting at 15 mph...
(x-15)/(15x)=1/20
x-15=15x/20
-15=15x/20-x
-15=-1/4x
x=60 miles per hour
If you wanted to save 3 minutes per mile when starting at 20 mph...
(x-20)/(20x)=1/20
-20=20x/20-x
-20=0 ...
Wait, what? ... oh right, you cant save 3 minutes when it only takes 3 minutes per mile @ 20 mph, hehe.

And if you wanted to save 6 minutes starting at 20mph, you would have to go -20mph, which is kind of theoretically possible since physics has negative velocities... just not negative speeds >.>.  I’m sure all it would take is one point twenty one jiggawatts to achieve.


If you’ve actually read this far without getting bored, I congratulate you :-).

Even more sad is the last Dallas-Austin drive I made in which I couldn’t remember the compound continually interest formula and spent a good chunk of the time deriving it in my head (all I could remember was the needed variables

“pert” - principle, e (~2.71 - exp), rate, time).