RSA Matlab

RSA Encryption

 RSA = Rivest, Shamir, and Adelman (MIT), 1978  Underlying hard problem

– Number theory – determining prime factors of a given (large) number

 e.g., factoring of small #: 5 -) 5, 6 -) 2 *3 – Arithmetic modulo n

 How secure is RSA? – So far remains secure (after all these years...) – Will somebody propose a quick algorithm to factor

large numbers?

– Will quantum computing break it? -) TBD

RSA Encryption

 In RSA: – P = E (D(P)) = D(E(P)) (order of D/E does not matter)

– More precisely: P = E(kE, D(kD, P)) = D(kD, E(kE, P))

 Encryption: C = Pe mod n KE = e – n is the key length – Note, P is turned into an integer using a padding

scheme

– Given C, it is very difficult to find P without knowing KD

 Decryption: P = Cd mod n KD = d  We will look at this algorithm in detail next time

RSA Algorithm

1. Key Generation

– A key generation algorithm

2. RSA Function Evaluation

– A function F, that takes as an input a point x and a key k and produces either an encrypted result or

plaintext, depending on the input and the key

Key Generation

 The key generation algorithm is the most complex part of RSA

 The aim of the key generation algorithm is to generate both the public and the private RSA keys

– Very important, weak key generation makes RSA very vulnerable to attack

Key Generation

1. Large Prime Number Generation – Two large prime numbers p and q need to be generated – These numbers are very large: at least 512 digits, but 1024 digits is considered

safe

2. Compute n = pq – n is used as the modulus for both the public and private keys

– Its length, usually expressed in bits, is the key length 3. Totient

– The totient of n,𝜙(n) is calculated 4. Public Key

– A prime number is calculated from the range [3,𝜙(n)) that has a GCD of 1 with 𝜙 (n )

5. Private Key – Because the prime in step 4 has a GCD of 1 with 𝜙(n), we are able to

determine it's inverse with respect to mod 𝜙(n)

Large Prime Number Generation

 It is vital for RSA security that two very large prime numbers be generated that are quite far apart

 Generating composite numbers, or even prime numbers that are close together makes RSA totally insecure

Large Prime Number Generation

 How does one generate large prime numbers?

 The answer is to pick a large random number (a very large random number) and test for primeness

 If that number fails the prime test, then add 1 and start over again until we have a number that passes a prime test

 The problem is now – How do we test a number in order to determine if it is

prime?

Large Prime Number Generation

 The answer...

– An incredibly fast prime number tester called the Rabin-Miller primality tester

 In Matlab, there is a command that implements this tester: “isprime”

 You will need to generate two large prime numbers: p and q

Large Prime Number Generation

Compute n = p• q

 Once we have our two prime numbers, we can compute n very easily:

n= p• q

 RSA’s main security foundation relies upon the fact that given two large prime numbers, a composite number (in this case n) can very easily be deduced by multiplying the two primes together

 But, given just n, there is no known algorithm to efficiently determining n’s prime factors – In fact, it is considered a hard math problem!

Totient

 With the prime factors of n, the totient can be very quickly calculated:

q 5𝑛 = (𝑝 1 ) • (𝑞 1 )

 It is derived like so: q5𝑛 = q5𝑝• 𝑞 = q5𝑝 • q5𝑞

= (𝑝 1) • (𝑞 1)

 The reason why the RSA becomes vulnerable is if one can determine the prime factors of 𝑛, then one can easily determine the totient

Public Key

 Normally expressed as e, it is a prime number chosen

in the range [3, 𝜙 𝑛 ) – You may think 3 is too small – I agree! – this could lead to

security flaws

 So in practice, the public key is normally set at 65537

 Is it a problem that this number is fixed?

– No, as long as the private key cannot be deduced from the public key

 The public key is actually a key pair of the exponent e and n and is present as follows

(𝑒, 𝑛)

Private Key

 Because the public key has a GCD of 1 with 0 n, the multiplicative inverse of the public key with respect to 0 n can be efficiently and quickly determined using the Extended Euclidean Algorithm

 This multiplicative inverse is the private key  The common notation for expressing the private key is d  So in effect, we have the following equation:

e• dE l mod 0 n – The expression e • d  1 mod 0 n, pronounced “e • d is congruent to

1 modulo 0 n ,” means that e • d 1 is a multiple of 0 n – We call e • d the residue of a modulo 0 n and write e • d = (1 mod

0 n )

 Just like the public key, the private key is also a key pair of the exponent d and modulus n:

(d, n)

Extended Euclidean Algorithm

 Since e is fixed, we can approximate d

– (e•d)-1 = i•c/ 𝑛 or (e•d) = i•c/ 𝑛 + 1  Where i is a positive integer

 We can loop though values of i starting at 1 while the following Euclidean remainder is greater than 0 (r > 0)

𝑟 = 𝑘 𝑚 𝑜 𝑑 𝑒

– Where k= i•c/𝑛 + 1  Once r is obtained, d is then given by d= k/e

49 =

7 = 7

𝑘

– 𝑑=

𝑒

Extended Euclidean Algorithm Example

 Let 𝑝= 3, 𝑞= 5, and

𝑒= 7

 𝜙𝑛= 𝑝 1 * 𝑞 1

=

2 * 4 = 8

 Now, the loop

– Do this loop while 𝑟> 0 – See table

 Finally, calculate 𝑑

𝑖 𝑟 𝑘

1 1 9

2 2 17 3 3 25

4 4 33 5 5 41

6 6 49 7 0

RSA Function Evaluation

 This is the process of transforming a plaintext message into ciphertext (or vice-versa)

 The RSA function, for message m and key k is evaluated as follows:

Fm, k = m'modn  There are obviously two cases:

1. Encrypting with the public key, and then decrypting with the private key

2. Encrypting with the private key, and then decrypting with the public key

RSA Function Evaluation

 The two cases above are mirrors

 I will explain the first case, the second follows from the first

 Encryption: F m, 𝑒 = m𝑒 mo𝑑 n = c, where m is the message, e is the public key and c is the cipher

 Decryption: F c, 𝑑 = c𝑑 mo𝑑 n =m

RSA Example

1. Calculation of n and Totient

– Lets choose two primes: p=11 and q=13

– Hence, n=p×q=143

– The totient of n 𝜙𝑛 = 𝑝 1 ∙ 𝑞 1 = 120

RSA Example

2. Key Generation – For the public key, a random prime number that has a GCD

of 1 with 𝜙 𝑛 and is less than 𝜙 𝑛 is chosen – Let’s choose 7

 Note, both 3 and 5 do not have a GCD of 1 with 𝜙 𝑛

– So e = 7, and to determine d, the secret key, we need to

find the inverse of 7 with 𝜙 𝑛 – This can be done very easily and quickly with the Extended

Euclidean Algorithm (see example above), and hence d = 103

– This can be easily verified using e d  1 mod 𝜙 𝑛  7103 = 721  1 mod 120  721-1 = 720 = 6*120

RSA Example

3. Encryption/Decryption

– Lets choose our plaintext message, m to be 9:

– Encryption: me mod n = 97 mod 143 = 48 = c

– Decryption: cd mod n = 48103 mod 143 = 9 = m

 NOTE: use the given “bigmod” function not the built in “mod” Matlab function

– “mod” will not work for large numbers

A Real World Example

 Let’s encrypt the message “attack at dawn”

 In this example, the message is convert to a bit array and then one large single number

– For the HW, we will just use ASCII

 “attack at dawn” becomes 1976620216402300889624482718775150

ASCII

 ASCII is a character-encoding scheme  The “double” command in Matlab

converts a string to ASCII

CAIIEORNIA STATE UNIVOLSITY

FULLERTON"

ASCII CHART

Dec Hex Char Dec Hex Char Dec Hex Char Dec Hex Char

0 00 Null 32 20 Space 64 40 @ 96 60 '

1. 01. Start of heading 65 41 A 97 61 a

34 22 " 66 42 B 98 62 b

3 03 End of text

if 67 43 C 99 63 c

rensmrt 36 24 $ 68 44 D 100 64 ci

05 Enquiry 37 25 % 69 45 E 101 65 e 5

6 05 Acknowledge 38 26 & 70 46 F 102 66 1

7 0'7 Audible bell 39 2'7 ' 71 67 G 103 67 9

8 08 Backspace 40 28 i 72 48 H 104 66 h

9 09 Horizontal tab 41. 29 1 73 49 I 105 69 i

10 OA Line feed 42 2A ,, 74 4A J 106 6A j

11 OH Vertical tab 43 26 + 75 4B X 107 6B k

12 02 Form reed 44 2C f 76 4C L 108 62 I.

13 OD Carriage return 45 2D - 77 4D N 109 6D m

14 OE Shift out 46 2E . 78 4E N 110 6E n

15 OF Shift In 47 2F / 79 4F 0 111 6F o

16 10 Data link escape 48 30 0 80 50 P 112 '70 9

1.7 11 Device control 1 49 3 1 1 81 51 0 113 '71 q

1.8 12 Device control 2 50 32 2 82 52 R 114 '72 r

1.9 13 Device control 3 51. 33 3 83 53 6 115 '73 a

14 Device control 4 52 34 4 84 54 T 116 74 t

21 eg acknowledge 53 35 5 85 55 U 11'7 75 u

16 22 Sy sidle 54 36 6 86 56 V 118 '76 v

23 17 Endtrans.blo 55 3'7 '7 8'7 57 11 119 '77 w

24 18 Cancel

8 8 88 58 X 120 '78 x

25 19 End of medium 57 32 89 59 Y 121 79 y

26 1A Substitution 58 3A : 90 5A Z 122 7A z

27 1B Escape 59 312 ; 91 5B [ 123 713 1

28 10 File separator 60 3C < 92 50 \ 124 70 I

29 10 Group separator 61 3D - 93 50 ] 125 7D )

30 12 Record separator 62 3E > 94 52 ' 126 7E -'

31 1F Unit separator 63 3F 2 95 5F 127 7F 0

9SSURSES

Code P

el: MARAB PM Fa - academic use

= :2/ Preferences Communal,

Lsy,„,t v_t Set Pat He„

>ksue, +Add,.

. 46 M 1-10 ® e f F Current

Fol der I Workspace ®

alibi t Oro taboo (Cal Fullerton) I CS LIF Related f Courses I EGCP- dlarne Value

a n s

C o m m a n d F l i s t r a y

r e a d ( 1 . 1 2 0 )

c i c

r e a d ( 7 . 1 0 0

1 1 x t ( 9 0 . 1 0 1

d o u b l e ( P )

d a u b . ° ( I V O

d o u b l e ( f a »

d o u b l e ( f t ,

d o u b l e ( . 6 . ) ,

c i c

c . v . °

c i c

d o u b l e ( f a »

c l o a » l e »

» doabl e •S • /

6 5

d o u b l e C B .

6 6

d o u b l e Z . )

9 0

A>

m - A feefert Save

Worlapace Clew Workspace 6 1:4Clerveenerancia 6 Libra,

Eta Pun ana Toe

t 6 : . 1

A Real World Example Key Generation

 Now we need to pick two large primes, p and q  These numbers must be random and not too close to each other  Here are numbers generated using the Rabin-Miller primality tests:  p

– 12131072439211271897323671531612440428472427633701410925 63454931230196437304208561932419736532241686654101705736 1365214171711713797974299334871062829803541

 q – 12027524255478748885956220793734512128733387803682075433

65389998395517985098879789986914690080913161115334681705 0832096022160146366346391812470987105415233

A Real World Example Key Generation

 With these two large numbers, we can calculate n and 𝜙 𝑛  n

– 14590676800758332323018693934907063529240187237535716439 95818710198734387990053589383695714026701498021218180862

92467422828157022922076746906543401224889672472407926969 98710058129010319931785875366371086235765651050788371429 71156373427889114635351027120327651665184117268598379886 72111837205085526346618740053

 𝜙 𝑛 – 14590676800758332323018693934907063529240187237535716439

95818710198734387990053589383695714026701498021218180862 92467422828157022922076746906543401224889648313811232279 96631730139777785236530154784827347887129722205858745715 28916064592697181192689711635550708026439995295496441168 11947516513938184296683521280

A Real World Example Key Generation

 e - the public key

– 65537 has a GCD of 1 with /. 𝑛, so lets use it as the public key – To calculate the private key, use extended Euclidean algorithm

to find the multiplicative inverse with respect to /. 𝑛

 d - the private key – 894894250092744443682285459217730939196695860658842

574454978544564876748396298183909349419732628796167 979706089172836798754993315741611138540888132754881 105882471930775825272784379065040156806234235500672 400424666656542323835029222154936232894721388664458 187891279461234078077257026266440910365023725451397 13

A Real World Example Encryption/Decryption

 Encryption

– 1976620216402300889624482718775150e mod n

– 3505211133867302669021242393705332851188 0760811579981620642802346685810623109850 2359430490809733862411137840407947041939 7821537849976541308364643878474095230693 2534945195080183861574225226218879827232 4539128205968864403775360824656817500744 1745915148540744586251102347223556082305 3497791518928820272257787786

A Real World Example Encryption/Decryption

 Decryption

– 35052111338673026690212423937053328511880760811 57998162064280234668581062310985023594304908097 33862411137840407947041939782153784997654130836 46438784740952306932534945195080183861574225226 21887982723245391282059688644037753608246568175 00744174591514854074458625110234722355608230534 97791518928820272257787786d mod n

 1976620216402300889624482718775150 (which is our plaintext “attack at dawn”)

 This real world example shows how large the numbers are that are used in the real world

HW 5-RSA/genPrivKey.m

function [n, d] = genPrivKey(p,q,e) % function [n, d] = genPrivKey(p,q,e) % % Generates the private key exponent and the modulus % % Inputs: % p: One of the prime numbers % q: The other prime numbers % e: Exponent of public key % % Outputs: % n: Modulus (length of keys) % d: Exponent of private key %