Scribd
Upload
62 views15 pages

Classical Number Theory and Modern Cryptography: Keith Jones Binghamton University

This document provides an introduction to classical number theory and its application to modern cryptography. It includes examples of simple ciphers like the Caesar cipher and monoalphabetic substitution cipher. It also provides an example of using the RSA encryption algorithm, showing how it works step-by-step to encrypt the message "HELLO". References for further reading on number theory and cryptography are also listed.

Uploaded by

millermaxf
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
62 views15 pages

Classical Number Theory and Modern Cryptography: Keith Jones Binghamton University

This document provides an introduction to classical number theory and its application to modern cryptography. It includes examples of simple ciphers like the Caesar cipher and monoalphabetic substitution cipher. It also provides an example of using the RSA encryption algorithm, showing how it works step-by-step to encrypt the message "HELLO". References for further reading on number theory and cryptography are also listed.

Uploaded by

millermaxf
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Classical Number Theory and Modern Cryptography

Keith Jones Binghamton University

February 2010

Table 1: The Caesar Cipher

Original: Shift 3: Original Shift 3:

A D N Q

B E O R

C F P S

D G Q T

E H R U

F I S V

G J T W

H K U X

I L V Y

J M W Z

K N X A

L O Y B

M P Z C

Table 2: A Monoalphabetic Substitution Cipher

Original: Shued: Original Shued:

A E N F

B K O Z

C G P B

D U Q S

E J R A

F L S O

G V T D

H C U P

I X V Q

J T W R

K Y X M

L N Y I

M H Z W

A Sample Cryptogram
A cryptogram on the beauty of cryptograms...

E.

Hints and solution available at: [Link]

Table 3: Conversion to Digits


A B C D E F G H I J K L M = = = = = = = = = = = = = 00 01 02 03 04 05 06 07 08 09 10 11 12 and space N = O = P = Q = R = S = T = U = V = W = X = Y = Z = = 99 13 14 15 16 17 18 19 20 21 22 23 24 25

RSA Example

1. Let p = 97 and q = 101.

RSA Example

1. Let p = 97 and q = 101. Then n = pq = 9797 and (n) = (p 1)(q 1) = 9600.

RSA Example

1. Let p = 97 and q = 101. Then n = pq = 9797 and (n) = (p 1)(q 1) = 9600. 2. Choose k = 23 and j = 2087. One can verify that k and (n) are relatively prime, and that kj 1 mod (n).

RSA Example

1. Let p = 97 and q = 101. Then n = pq = 9797 and (n) = (p 1)(q 1) = 9600. 2. Choose k = 23 and j = 2087. One can verify that k and (n) are relatively prime, and that kj 1 mod (n). 3. We will encrypt the message HELLO. We will encode letters using the previously described mechanism: A 00, B 01, etc.

RSA Example, continued. (n = 9797, k = 23, j = 2087)


H 07 E 04 L 11 L 11, again O 14 So HELLO becomes 0704111114.

RSA Example, continued. (n = 9797, k = 23, j = 2087)


H 07 E 04 L 11 L 11, again O 14 So HELLO becomes 0704111114. We will use blocks of length 3 . Since we have 10 digits, well add a space (99). M = 070411111499 070 411 111 499. Note this technically isnt small enough to guarantee that each block will be relatively prime to n.

RSA Example, continued. (n = 9797, k = 23, j = 2087)

070 7023 mod 9797 7002 411 41123 mod 9797 8208 111 11123 mod 9797 4131 499 49923 mod 9797 4228

RSA Example, continued. (n = 9797, k = 23, j = 2087)

070 7023 mod 9797 7002 411 41123 mod 9797 8208 111 11123 mod 9797 4131 499 49923 mod 9797 4228 Cipher: 7002 8208 4131 4228

RSA Example, continued. (n = 9797, k = 23, j = 2087)

070 7023 mod 9797 7002 411 41123 mod 9797 8208 111 11123 mod 9797 4131 499 49923 mod 9797 4228 Cipher: 7002 8208 4131 4228 7002 70022087 8208 82082087 4131 41312087 4228 42282087 mod mod mod mod 9797 70 9797 411 9797 111 9797 499

References and Further Reading


Elementary Number Theory, David M. Burton The Art of Proof, Matthias Beck & Ross Geoghegan
free at [Link] Appendix B on Die-Hellman

The (simple) mathematics of RSA. Martin Ouwehand.


Essay at [Link]

Disquisitiones Arithmeticae. Carl Friedrich Gauss.


Available at Google Books.

...and of course WikipediA

You might also like