$SPAD/src/input rsa.input

Timothy Daly December 3, 2016

Abstract

Contents

2

— rsatest.input —

)set break resume
)sys rm -f rsa.output
)spool rsa.output
)set message test on
)set message auto off
)clear all

———-

First we extract the spad code into an input file — * —

)sys cp $AXIOM/../../src/input/rsa.input.pamphlet .
)lisp (tangle "rsa.input.pamphlet" "rsatest.input" "rsatest.input")
)read rsatest

———-

1 Overview

RSA is an encryption algorithm that relies on knowing that factoring is difficult. RSA stands for Ron Rivest, Adi Shamir, and Leonard Adleman who described the algorithm in 1977 [?]. From Wikipedia [?]:

• Choose two distinct prime numbers p and q

– For security purposes, the integers p and q should be chosen at random, and should be of similar bit-length. Prime integers can be efficiently found using a primality test.

• Compute n = pq

– n is used as the modulus for both thhe public and private keys. Its length, expressed in bits, is the key length.

• Compute ϕ(n) = (p − 1)(q − 1), where ϕ is Euler’s totient function

• Choose an integer e such that 1 < e < ϕ(n) and gcd(e, ϕ(n)) = 1, that is, e and ϕ(n) are coprime.

– e is released as the public key exponent

– e having a short bit-length and small Hamming weight results in more efficient encryption – most commonly 2^{16} + 1 = 65537. However, much smaller values of e (such as 3) have been shown to be less secure in some settings.

• Determine d as d ≡ e^{−1}(mod ϕ(n)), i.e. d is the multiplicitive inverse of e(modulo ϕ(n))

– This is more clearly stated as solve for d given de ≡ 1 (mod ϕ(n))

– This is often computed using the Extended Euclidean algorithm – d is kept as the private key exponent

By construction d ∗ e ≡ 1(mod ϕ(n)). The public key consists of the modulus n and the public (or encryption) exponent e. The private key consists of the modulus n and the private (or decryption) exponent d, which must be kept secret. p, q, and ϕ(n) must also be kept secret because they can be used to calculate d.

2 Key Generation

For the purpose of this example, our public key will consist of two values (N and E). Our private key will also consist of two values (N and D). The first step of the key generation phase is to pick two different prime numbers. In our running example, we will choose the values P = 61 and Q = 53.

— rsatest.input —

--S 1 of 13
P := 61
--R
--R
--R   (1)  61
--R                                                        Type: PositiveInteger
--E 1
--S 2 of 13
Q := 53
--R
--R
--R   (2)  53
--R                                                        Type: PositiveInteger
--E 2

———-

The next step is to calculate N - which is simply just the product of P ∗ Q.

N = P ∗ Q
N = 61 ∗ 53 = 3233

— rsatest.input —

--S 3 of 13
N := P * Q
--R
--R
--R   (3)  3233
--R                                                        Type: PositiveInteger
--E 3

———-

We must then calculate Euler’s totient function for N. Put more clearly, find the product of (P − 1) ∗ (Q − 1).

totient(N) = (P − 1)(Q − 1)

totient(N) = (61 − 1)(53 − 1)

totient(N) = 3120

— rsatest.input —

--S 4 of 13
totient := (P-1)*(Q-1)
--R
--R
--R   (4)  3120
--R                                                        Type: PositiveInteger
--E 4

———-

To choose E, we must pick an integer such that 1 < E < 3120 that is coprime to 3120. Meaning to pick E, we must satisfy two conditions. First, E must be greater than one but less than our totient(N) value of 3120. Secondly, E must also be coprime to 3120. In order to be coprime, the greatest common divisor (gcd) of totient(N) and E must equal one.

— rsatest.input —

--S 5 of 13
t1:=[x for x in 1..totient | gcd(totient,x) = 1]
--R
--R   (5)
--R   [1, 7, 11, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73,
--R    77, 79, 83, 89, 97, 101, 103, 107, 109, 113, 119, 121, 127, 131, 133, 137,
--R    139, 149, 151, 157, 161, 163, 167, 173, 179, 181, 187, 191, 193, 197, 199,
--R    203, 209, 211, 217, 223, 227, 229, 233, 239, 241, 251, 253, 257, 259, 263,
--R    269, 271, 277, 281, 283, 287, 289, 293, 301, 307, 311, 313, 317, 319, 323,
--R    329, 331, 337, 341, 343, 347, 349, 353, 359, 361, 367, 371, 373, 379, 383,
--R    389, 391, 397, 401, 407, 409, 413, 419, 421, 427, 431, 433, 437, 439, 443,
--R    449, 451, 457, 461, 463, 467, 469, 473, 479, 487, 491, 493, 497, 499, 503,
--R    509, 511, 517, 521, 523, 527, 529, 539, 541, 547, 551, 553, 557, 563, 569,
--R    571, 577, 581, 583, 587, 589, 593, 599, 601, 607, 613, 617, 619, 623, 629,
--R    631, 641, 643, 647, 649, 653, 659, 661, 667, 671, 673, 677, 679, 683, 691,
--R    697, 701, 703, 707, 709, 713, 719, 721, 727, 731, 733, 737, 739, 743, 749,
--R    751, 757, 761, 763, 769, 773, 779, 781, 787, 791, 797, 799, 803, 809, 811,
--R    817, 821, 823, 827, 829, 833, 839, 841, 847, 851, 853, 857, 859, 863, 869,
--R    877, 881, 883, 887, 889, 893, 899, 901, 907, 911, 913, 917, 919, 929, 931,

--R    937, 941, 943, 947, 953, 959, 961, 967, 971, 973, 977, 979, 983, 989, 991,
--R    997, 1003, 1007, 1009, 1013, 1019, 1021, 1031, 1033, 1037, 1039, 1043,
--R    1049, 1051, 1057, 1061, 1063, 1067, 1069, 1073, 1081, 1087, 1091, 1093,
--R    1097, 1099, 1103, 1109, 1111, 1117, 1121, 1123, 1127, 1129, 1133, 1139,
--R    1141, 1147, 1151, 1153, 1159, 1163, 1169, 1171, 1177, 1181, 1187, 1189,
--R    1193, 1199, 1201, 1207, 1211, 1213, 1217, 1219, 1223, 1229, 1231, 1237,
--R    1241, 1243, 1247, 1249, 1253, 1259, 1267, 1271, 1273, 1277, 1279, 1283,
--R    1289, 1291, 1297, 1301, 1303, 1307, 1309, 1319, 1321, 1327, 1331, 1333,
--R    1337, 1343, 1349, 1351, 1357, 1361, 1363, 1367, 1369, 1373, 1379, 1381,
--R    1387, 1393, 1397, 1399, 1403, 1409, 1411, 1421, 1423, 1427, 1429, 1433,
--R    1439, 1441, 1447, 1451, 1453, 1457, 1459, 1463, 1471, 1477, 1481, 1483,
--R    1487, 1489, 1493, 1499, 1501, 1507, 1511, 1513, 1517, 1519, 1523, 1529,
--R    1531, 1537, 1541, 1543, 1549, 1553, 1559, 1561, 1567, 1571, 1577, 1579,
--R    1583, 1589, 1591, 1597, 1601, 1603, 1607, 1609, 1613, 1619, 1621, 1627,
--R    1631, 1633, 1637, 1639, 1643, 1649, 1657, 1661, 1663, 1667, 1669, 1673,
--R    1679, 1681, 1687, 1691, 1693, 1697, 1699, 1709, 1711, 1717, 1721, 1723,
--R    1727, 1733, 1739, 1741, 1747, 1751, 1753, 1757, 1759, 1763, 1769, 1771,
--R    1777, 1783, 1787, 1789, 1793, 1799, 1801, 1811, 1813, 1817, 1819, 1823,
--R    1829, 1831, 1837, 1841, 1843, 1847, 1849, 1853, 1861, 1867, 1871, 1873,
--R    1877, 1879, 1883, 1889, 1891, 1897, 1901, 1903, 1907, 1909, 1913, 1919,
--R    1921, 1927, 1931, 1933, 1939, 1943, 1949, 1951, 1957, 1961, 1967, 1969,
--R    1973, 1979, 1981, 1987, 1991, 1993, 1997, 1999, 2003, 2009, 2011, 2017,
--R    2021, 2023, 2027, 2029, 2033, 2039, 2047, 2051, 2053, 2057, 2059, 2063,
--R    2069, 2071, 2077, 2081, 2083, 2087, 2089, 2099, 2101, 2107, 2111, 2113,
--R    2117, 2123, 2129, 2131, 2137, 2141, 2143, 2147, 2149, 2153, 2159, 2161,
--R    2167, 2173, 2177, 2179, 2183, 2189, 2191, 2201, 2203, 2207, 2209, 2213,
--R    2219, 2221, 2227, 2231, 2233, 2237, 2239, 2243, 2251, 2257, 2261, 2263,
--R    2267, 2269, 2273, 2279, 2281, 2287, 2291, 2293, 2297, 2299, 2303, 2309,
--R    2311, 2317, 2321, 2323, 2329, 2333, 2339, 2341, 2347, 2351, 2357, 2359,
--R    2363, 2369, 2371, 2377, 2381, 2383, 2387, 2389, 2393, 2399, 2401, 2407,
--R    2411, 2413, 2417, 2419, 2423, 2429, 2437, 2441, 2443, 2447, 2449, 2453,
--R    2459, 2461, 2467, 2471, 2473, 2477, 2479, 2489, 2491, 2497, 2501, 2503,
--R    2507, 2513, 2519, 2521, 2527, 2531, 2533, 2537, 2539, 2543, 2549, 2551,
--R    2557, 2563, 2567, 2569, 2573, 2579, 2581, 2591, 2593, 2597, 2599, 2603,
--R    2609, 2611, 2617, 2621, 2623, 2627, 2629, 2633, 2641, 2647, 2651, 2653,
--R    2657, 2659, 2663, 2669, 2671, 2677, 2681, 2683, 2687, 2689, 2693, 2699,
--R    2701, 2707, 2711, 2713, 2719, 2723, 2729, 2731, 2737, 2741, 2747, 2749,
--R    2753, 2759, 2761, 2767, 2771, 2773, 2777, 2779, 2783, 2789, 2791, 2797,
--R    2801, 2803, 2807, 2809, 2813, 2819, 2827, 2831, 2833, 2837, 2839, 2843,
--R    2849, 2851, 2857, 2861, 2863, 2867, 2869, 2879, 2881, 2887, 2891, 2893,
--R    2897, 2903, 2909, 2911, 2917, 2921, 2923, 2927, 2929, 2933, 2939, 2941,
--R    2947, 2953, 2957, 2959, 2963, 2969, 2971, 2981, 2983, 2987, 2989, 2993,
--R    2999, 3001, 3007, 3011, 3013, 3017, 3019, 3023, 3031, 3037, 3041, 3043,
--R    3047, 3049, 3053, 3059, 3061, 3067, 3071, 3073, 3077, 3079, 3083, 3089,
--R    3091, 3097, 3101, 3103, 3109, 3113, 3119]
--R                                                  Type: List(PositiveInteger)
--E 5

———-

Let’s try 17. It satisfies our first condition as 17 is greater than 1 and also less than 3120.

Let’s check the second condition. Since 1 is in fact the largest divisor common to 3120 and 17, we have satisfied both conditions.

E = 17

— rsatest.input —

--S 6 of 13
E := t1.4
--R
--R
--R   (6)  17
--R                                                        Type: PositiveInteger
--E 6

———-

The last value that we need to compute is D. D is the modular multiplicative inverse of E mod totient(N). In order to compute D, we will have to find (17^{−}1) = D(mod 3120) which is the same as 17 ∗ D = 1 mod(3120). That is, we must find a number D that when multiplied by 17 and modulus divided by 3120 will have a remainder of 1. The easiest way to determine D is to iterate the value of D from 0 onward until both conditions are satisfied. There are more efficient ways of performing this calculation, using the Extended Euclidean Algorithm. In our case, 17 will satisfy these conditions.

D ∗ 17(mod 3120) = 1

2753 ∗ 17 = 46801
46801 mod 3120 = 1
D = 2753

— rsatest.input —

--S 7 of 13
ttn:=IntegerMod(totient)
--R
--R
--R   (7)  IntegerMod(3120)
--R                                                                 Type: Domain
--E 7
--S 8 of 13
D := [x for x in 1..totient | (x*E)::ttn = 1].1
--R
--R
--R   (8)  2753
--R                                                        Type: PositiveInteger
--E 8

———-

We now have our public key (N and E) and our private key (N and D).

— rsatest.input —

--S 9 of 13
[N,E]
--R
--R
--R   (9)  [3233,17]
--R                                                  Type: List(PositiveInteger)
--E 9
--S 10 of 13
[N,D]
--R
--R
--R   (10)  [3233,2753]
--R                                                  Type: List(PositiveInteger)
--E 10

———-

3 Encryption

We have completed the key generation phase. We have all the components needed to encrypt and decrypt a message. The encryption and decryption used in RSA are performed by using modular exponentiation. A modular exponentiation takes the form:

C = M^{E}modN

Encode the message as an integer M. Take an integer message M and raise it to the E^{th} power, then modulus divide by N. Back to our example, we will pick a plaintext message of 65 to encrypt. So we have message M = 65. The output of this step, C, will be our ciphertext. Our encryption function is just like the modular exponentiation example above. It will be in the form.

C = M^{E} (mod N)

We just need to substitute our values from the running example. This will give us.

C = 65^{17} (mod 3233)

C = 2790

— rsatest.input —

--S 11 of 13
M := 65
--R
--R
--R   (11)  65
--R                                                        Type: PositiveInteger
--E 11
--S 12 of 13
C := (M^E)::IntegerMod(N)
--R
--R
--R   (12)  2790
--R                                                       Type: IntegerMod(3233)
--E 12

———-

4 Decryption

Now, to decrypt this message we will do another modular exponentiation in the form:

M = C^{D} (mod N)

Again, we just substitute our values. This will give us:

M = 2790^{2753} (mod 3233)

M = 65

which is our original message.

— rsatest.input —

--S 13 of 13
(C^D)::IntegerMod(N)
--R
--R
--R   (13)  65
--R                                                       Type: IntegerMod(3233)
--E 13
)spool
)lisp (bye)

———-

References

[1] Rivest, R., Shamir, A., Adleman, L. “A Method for Obtaining Digitial Signatures and Public-Key Cryptosystems” CACM 21 (2) pp120-126 1978

[2] http://en.wikipedia.org/wiki/RSA_(algorithm)