1 of 9

Number Theory and Cryptography

Owen Blume

2 of 9

Caesar Cipher

JGNNQ

HELLO

3 of 9

Congruence/Modulo Theory

4 of 9

Prelude to RSA Encryption

5 of 9

Prelude to RSA Encryption (Continued)

6 of 9

RSA Encryption

NO WAY TODAY

131426220024261914030024

124118480873161420810873

7 of 9

RSA Encryption (Math)

8 of 9

RSA Decryption (Math)

Now to decrypt this, it is important to note that n and k are in a public file, meaning anyone can access it. So we have access to n and k and we will also be given access to the two primes that were used to find n which for us were 37 and 73, however these numbers are a private key.. What we need to find is some j which is our recovery exponent which must satisfy the statement kj is congruent 1 mod phi n. Our encrypted value, r, to the j power must be congruent our original value M to the k*j power. Because kj is congruent 1 mod phi n, we can write kj as 1+ (phi n times some t). Now, using Euler’s generalization of Fermat’’s little theorem we know that an integer to the power phi n is congruent 1 mod n. We can use this to simplify our congruence down to the statement M times 1 to the power t is congruent M mod n. This proves why the power j will work in allowing us to recover our plaintext numbers. In order to actually decrypt the message the recipient uses the Euclidian algorithm, in this case, to get the equation 47*1103+2592*(-20)=1. This means that our j is 1103. Now to decrypt we simply take our block of encrypted code for example the 1241 at the beginning and raise it to the 1103 power and find that this number mod 2701, our n, is 1314 which is the original number before encryption.

9 of 9

RSA Encryption

NO WAY TODAY

131426220024261914030024

124118480873161420810873