Applications of Number Theory in Computer Science Curriculum

Ciphertext Only Cryptanalytic Attack on MerkleHellman Knapsack: Dynamic Programming Algorithm Input: A={a1, a2, an} public key, S - ciphertext Output: The binary array B plaintext Algorithm: Let P[i, j] be TRUE if there is a subset of first i elements of A that sums to j, 0 i n , 0 j S Step 1: Computation of P P[0][0] TRUE for j = 1 to S do: P[0][j] FALSE for i = 1 to n do: for j = 0 to S do: if (j A[i] < 0): P[i][j] = P[i-1][j] else: P[i][j] = P[i-1][j-A[i]] or P[i-1][j] Step 2: Backtracking Let B be an array of n + 1 elements initialized to 0 i n, j S while i > 0: if (j A[i]) 0): if (P[i-1][j-A[i]] is True): B[i] B[i] + 1 j j A[i] ii1 else: i i 1 Output: array B, elements of B that equal to 1 construct a desired subset of A that sums to S EXAMPLE

Input: A={1, 4, 5, 2}, S =3 j=0 j=1 j=2 j=3 i=0 TRUE FALSE FALSE FALSE i=1 A[1] =1 TRUE TRUE FALSE FALSE i=2 A[2] = 4

TRUE TRUE FALSE FALSE i=3 A[3] = 5 TRUE TRUE FALSE FALSE i=4 A[4] = 2 TRUE TRUE TRUE TRUE Element is taken

Element is taken P[i-1][j-A[i]] or P[i-1][j] Merkle-Hellman Multiplicative Knapsack Cryptosystem Alice: Chooses set of relatively prime numbers P = {p1, pn} private (easy) knapsack Chooses prime M > p1* * pn Chooses primitive root b mod M Computes the public (hard) knapsack A = {a1, .an}, where ai is discrete logarithm of pi to base b: ai p b (mod M ) i 1 ai < M, such that:

Private Key: P, M, b Public Key: A Merkle-Hellman Multiplicative Knapsack Cryptosystem- Encryption Binary Plaintext T breaks up into sets of n elements long: T = {T1, Tk} n For each set Ti compute j 1 T ij a j C i Ci is the ciphertext that corresponds to plaintext Ti C = {C1, Ck) is ciphertext that corresponds to the plaintext T C is sent to Alice Merkle-Hellman Multiplicative

Knapsack Cryptosystem- Decryption For each Ci computes S i b C (mod M ) i Si is a subset product of the easy knapsack: n S i b Ci b Tij a j j 1 n b j 1 Tij a j n (b a j Tij ) j 1

Tij = 1 if and only if pj divides Si n j 1 Tij p j (mod M ) Merkle-Hellman Multiplicative Knapsack Example Easy (Private) Knapsack: P = {2, 3, 5, 7} M = 211, b = 17 Hard (Public) Knapsack: A= {19, 187, 198, 121} 2 1719(mod 211), 3 17187(mod 211), 5 17198(mod 211), 7 17121(mod 211) Plaintext: T = 1101 Ciphertext: C = 327 = 19 + 187 + 121 Decryption: S = 42 = 17327(mod 211) 42 = 21 * 31 *50 * 71 Plaintext: 1101