Number Theory and Cryptography

4.1 Divisibility and Modular Arithmetic 4.3 Primes and Greatest Common Divisor 4.6 Cryptography

Exercise 1: Show that 100 is composite?

Exercise 2: Show that 101 is prime?

Exercise 3: Find the prime factors of 7007?

·What time it will be (on a 24-hour clock) 50 hours from 11 am?

·After 24 hours it will be 11 am ·After another 24 hours it will be 11 am

• This is after 48 hours

·After 2 more hours it will be 13 (1 pm)!

• This is after 50 hours

·Is there another way?

·What time it will be (on a 24-hour clock) 50 hours from 11 am?

· Calculate (11 + 50) mod 24?

·We can also use mod Function to convert time from 24-hour clock to 12-hour

clock

·Calculate 13 mod 12?

·Calculate 23 mod 12?

Classical Cryptography Cryptosystems Public Key Cryptography RSA Cryptosystem Cryptographic Protocols Primitive Roots and Discrete Logarithms

Cryptography is a science that applies complex mathematics and

logic to design strong encryption methods.

Cryptography is also an art.

Cryptography allows people to keep confidence in the electronic

world.

People can do their business on electric channel without worrying of

deceit and deception.

Symmetric Encryption (single-key encryption)

Public Key Cryptography

All classical ciphers, including shift and affine ciphers, are private key cryptosystems. Knowing the encryption key allows one to quickly determine the decryption key.

All parties who wish to communicate using a private key cryptosystem must share the key and keep it a secret.

In public key cryptosystems, first invented in the 1970

s, knowing how to

encrypt a message does not help one to decrypt the message. Therefore, everyone can have a publicly known encryption key. The only key that needs to be kept secret is the decryption key.

The RSA algorithm involves four steps: key generation, key distribution, encryption and decryption.

The public encryption key is (n,e ), where n = pq, the modulus is the product of two large primes p and q ,say with 200 digits each, and an exponent e that is relatively prime to (p

q

The two large primes can be quickly found using probabilistic primarily

−1)(−1).

tests, discussed earlier.

But

n = pq, with approximately 400 digits, cannot be factored in a reasonable

length of time.

Step-1: Select two prime numbers p and q where p ≠ q.

Step-2: Calculate n = p * q.

Step-3: Calculate n) = (p-1) * (q-1).

Ф(

Step -4: Select e such that, e is relatively prime to n), i.e. (e, n)) = 1 and 1 < e < n)

Ф(

Ф(

Ф(

Step-5: Calculate d = e -1 mod n) or ed = 1 mod n).

Ф(

Ф(

Step-6: Public key = {e, n}, private key = {d, n}.

Step-7: Find out cipher text using the formula, C = P

e mod n where, P < n where C = Cipher text, P = Plain text, e = Encryption key and n=block size.

Step-8: P = C

d mod n. Plain text P can be obtain using the given formula. where, d =decryption key

Step 1: Select two prime numbers p and q where p ≠ q.

• Example, Two prime numbers p = 13, q = 11.

Step – 2: Calculate n = p * q.

Example, n = p * q = 13 * 11 = 143.

Step – 3: Calculate Ф(n) = (p

-1) * (q-1).

Example, Ф(n) = (13 –

1. * (11 – 1) = 12 * 10 = 120.

Step – 4: Select e such that,

1. coprime with n and Ф(n), i.e. (e, Ф(n)) = 1 and

2- 1 < e < Ф(n).

Example, Select e = 13, gcd (13, 120) = 1.

Step – 5: Calculate d = e -1 mod n) or e * d = 1 mod n)

Ф(

Ф(

Example, Finding d: e * d mod n) = 1

Ф(

13 * d mod 120 = 1 (How to find: d *e = 1 mod n) d = ((n) * i) + 1) / e



Ф(

Ф(

d = (120 + 1) / 13 = 9.30 (i = 1) d = (240 + 1) / 13 = 18.53 (i = 2)

∵

d = (360 + 1) / 13 = 27.76 (i = 3)

∵

d = (480 + 1) / 13 = 37 (i = 4))

∵

∵

Step – 6: Public key = {e, n}, private key = {d, n}.

Example, Public key = {13, 143} and private key = {37, 143}.

Step – 7: Find out cipher text C using the formula, C = P e mod n where, P < n.

Encryption Example, Plain text P = 13. (Where, P < n) C = P e mod n = 13 13 mod 143 = 52.

Step – 8: P = C

d mod n. Plain text P can be obtain using the given formula.

Decryption Example, Cipher text C = 52 P = C d mod n = 52 37 mod 143 = 13.

Encrypt (C = P

e mod n) the message B using the RSA cryptosystem with key

(5,14):

5 mod14= 32 mod 14 = 4

2 4 D



Decrypt (P = C

d mod n) the cipher text D using the RSA cryptosystem with key

(11,14):

4 mod 14 =4194304 mod 14 ≈2

11

2 B



Example: The message 0981 0461

is received. What is the decrypted message if it was

encrypted using the RSA cipher from the previous example.

Solution: The message was encrypted with

n = 43 59 = 2537 and exponent 13. An inverse

of 13 modulo 42 58 = 2436 (

exercise in Section 4.4) is d

= 937.

C M C 937 mod 2537.

∙

• To decrypt a block, = ∙
• Since 0981 937 mod 2537 = 0704 and 0461 mod 2537 = 1115, the decrypted message is 0704 937 1115. Translating back to English letters, the message is HELP.
• Here is a link to RSA calculator: https://www.cs.drexel.edu/~jpopyack/IntroCS/HW/RSAWorksheet.html

The Diffie Hellman algorithm widely known as Key exchange algorithm or key agreement algorithm developed by Whitefield Diffie and Martin Hellman in 1976. The purpose of the algorithm is to enable two users to securely exchange a key that can be used for subsequent encryption of messages. The algorithm itself is limited to the exchange of secret values.

Step-1: Select q (prime number) and is primitive root of q)

α (α

Step-2: User A Key Generation: select X, X < q

A A

Calculate public key Y, Y = X mod q

α

A A A

Y Shared with user B

A

Step-3: User B Key Generation: select X, X < q

B B

Calculate public key Y, Y = α

X mod q

B B B

Y shared with user A

B

Step-4: Calculation of secret key by user A: K = (Y) X mod q

B A

Step-5: Calculation of secret key by user B: K = (Y) X mod q

A B

Step – 4: Calculation of secret key by user A:

K = (Y) X mod q

B A

Example, Here Y = 4, X = 6

B

A

Calculate K = (Y)

X mod q 4 mod 7 1

B A

Step – 5: Calculation of secret key by user B:

⇒

⇒

K = (Y)

X mod q

A B

Example, Here Y = 1, X = 4

A

B

Calculate K = (Y) X mod q 1 4 mod 7 1

A B

⇒

⇒