RSA Cryptography

Initialisatie

stringshift[s_, n_] := 
      Module[{code, len, k}, 
code = 
          ToCharacterCode[s]; 
len = 
          Length[code]; 
For[k = 1, 
          k ≤ 
            len, k++, 
If[(code[[k]] ≥ 65) && (code[[k]] ≤ 
                  90), 
code[[k]] = 
              65 + Mod[code[[k]] - 65 + n, 
                  26]
]
]; 
Return[
          FromCharacterCode[code]]
]

SetAttributes[stringshift, Listable];

poemprint[p_] := 
      Module[{len = Length[p], k}, 
For[k = 1, 
          k ≤ len, k++, 
          Print[p[[k]]]
]
]

codedpoem = stringshift[poem, 10];

rep[n_] := (10^n - 1)/9

nextprime[n_] := 
      Module[{x = 
            n}, 
While[! PrimeQ[
              x], x++]; 
Return[
          x]
]

SetAttributes[mod, HoldAll]

mod[x_, m_] := 
      Module[{arg1}, 
arg1 = 
          ReleaseHold[Hold[x] /. Power -> List]; 
If[
          Length[arg1] > 1, 
Return[
            PowerMod[arg1[[1]], arg1[[2]], 
              m]], 
Return[
            Mod[x, m]]
]
]

makekey[e_, p_, q_] := 
      Module[{}, 
If[
          GCD[e, (p - 1)*(q - 1)] > 
            1, 
Print["Geen sleutel mogelijk, probeer \
andere waarde"]; 
Return[0]]; 
Return[
          PowerMod[
            e, -1, (p - 1)*(q - 
                  1)]]
]

randominteger[n_] := Random[Integer, {10^(n - 1), 10^n}]

randomprime[n_] := nextprime[randominteger[n]]

text2number[s_] := FromDigits[ToCharacterCode[s], 128]

number2text[n_] := FromCharacterCode[IntegerDigits[n, 128]]

Public Key Cryptografie

Suppose Bob wants to make a code to receive email messages without worrying about eavesdroppers. He uses a crypto system with a public key.  First he produces two prime numbers and their product.

p=randomprime[50]
q=randomprime[50]
n=p*q

Bob chooses 101 as public key (it could be any other number) and calls it  public. Next Bob computes the secret key which he calls  private.

public=101
private=makekey[public,p,q]

Then  Bob destroys the numbers p and q. For all numbers we have

(a^(public* private)) = a modulo n

For example:

mod[(11111^(public*private)),n]

Written differently:

((((a^public)))^private) = a modulo n

In other words: if we raise a number to the power PUBLIC and raise the result to the power PRIVATE we recover the number we started with.

Now Alice wishes to send a message to Bob. Bob has published his public key  public together with the number n. Bob carefully keeps the secret key  private. 

Here is the message Alice wishes to send:
    
Today we eat Brussel sprouts
First Alice turns this message into a number::

message = text2number["Today we eat Brussel sprouts"]

This message can easily be decoded:

number2text[message]

Alice cannot send this over the internet. First Alice encrypts the message with Bob's public key as follows:

codedmessage=mod[(message^public),n]

This can be sent by Alice over the internet. It is unreadible

number2text[codedmessage]

Bob receives the coded message and decodes it with his private key

decoded=mod[(codedmessage^private),n]

This number should give us the original message

number2text[decoded]

How can an eavesdropper crack this code? He only knows the numbers public and n. The only way to recover private is via the prime factors  p and q of n. There is the snag, large numbers are impossible to factor, p and q cannot be recovered!!  at least not in practice.

We call this procedure RSA-cryptography, after its inventors Rivest-Shamir-Adleman.

Of course Bob en Alice need not worry about manufactoring prime numbers and computations with big integers. This is all taken care of with standard software. A well-known program is PGP (Pretty Good Privacy).