Iams Post. June 12/94 The plaintext messsage was "Leonard Euler Pi", which was deciphered by David Wagner of Princeton. It is Euler's Totient Function that is the mathematical basis for the RSA Cryptographic System, hence the message. The trailing "Pi" was included to minimize the possibility of a "lucky guess". The 'cheap' scientific calculator, referred to in the original posting, was an old Radio Shack EC-4024, programmable. The problem itself, however, was set up on a 386DX using MathCAD and Qbasic. Below, is a detailed method for deciphering the encrypted message, a brief explanation of some of the how's and why's, and a copy of the original problem posting. Thanx. David *------------------------------------------------------------------------* A Cryptographic Problem ---------------------------------> The Solution: *------------------------------------------------------------------------* N = p*q (p) and (q) both prime PUBLIC Phi(N) = (p-1)(q-1) Totient function (Euler) E = Integer (E)nciphering Key PUBLIC -1 D = E mod Phi(N) (D)eciphering key PRIVATE *-------* STEP #1: *------------------------------------------------------------------------* You're given: E = 2683 N = 83323 N = p*q (p) & (q) both prime By factoring: p = 97 q = 859 Then: Phi(N) = (97-1)(859-1) Phi(N) = 82368 *-------* STEP #2: *------------------------------------------------------------------------* -1 You're given: D = E mod Phi(N) DE = 1 mod Phi(N) 1 = DE mod Phi(N) Then: 1 = DE - (k * Phi(N)) Algebraic form of equation DE = 1 + (k * Phi(N)) D = 1 + (k * 82368) Where D must be integer --------------- E D = 1 + (k * 82368) --------------- 2683 Set k = 1,2,3, ... i Trial and error .. k = 10 D = 1 + (10 * 82368) ---------------- 2683 D = 307 !THIS IS THE DECIPHERING KEY! *------------------------------------------------------------------------* *-------* STEP #3: *------------------------------------------------------------------------* To recover the plaintext: D P = C mod N 1 1 307 P = 48284 mod 83323 See NOTE 1 1 P = 3805 1 Look up (38) and (05) in the encoding alphabet: M = L e 1 Repeat STEP #3 for the remaining (C)iphertext blocks to obtain: Message = L e o n a r d E u l e r P i Plaintext = 3805 1514 0118 0463 3121 1205 1863 4209 Ciphertext= 48284 65276 34353 19422 26879 31970 31567 52773 *-------* NOTE 1: *------------------------------------------------------------------------* 307 The number 48284 is very large, so break up the process and handle it piece meal as follows. 1 1 2 (C mod N)(C mod N) mod N = C mod N 2 1 3 (C mod N)(C mod N) mod N = C mod N 3 1 4 (C mod N)(C mod N) mod N = C mod N etc. 4 4 8 (C mod N)(C mod N) mod N = C mod N 8 8 16 (C mod N)(C mod N) mod N = C mod N 16 16 32 (C mod N)(C mod N) mod N = C mod N etc. Hint: (256+32+16+3) = 307 2 The largest number to be processed is then C , (11 digits) max. *------------------------------------------------------------------------* *------------------------------------------------------------------------* How it all works ........... and why! *------------------------------------------------------------------------* N = p*q (p) and (q) both prime PUBLIC Phi(N) = (p-1)(q-1) Totient function (Euler) E = Integer (E)nciphering Key PUBLIC -1 D = E mod Phi(N) (D)eciphering key PRIVATE 1 = ED mod Phi(N) See below !!! The sender enciphers her/his (P)laintext message, P, into (C)iphertext blocks using the published, public keys E and N, as follows, E E C = P mod N ---------> C mod N = P mod N The receiver deciphers the (C)iphertext blocks by using her/his private key D, and the public key N, as follows, D D ED P = C mod N ---------> C mod N = P mod N This is possible because the arithmetic performed in the exponent is done Phi(N), such that, Y (Y mod Phi(Z)) X mod Z = X *------------------------------------------------------------------------* D ED (ED mod Phi(N)) So: C mod N = P mod N = P But: ED mod Phi(N) = 1 See above !!! D ED 1 So: C mod N = P mod N = P The Original Plaintext Block! *------------------------------------------------------------------------* It is Euler's Totient Function that makes it all work. Hence the message. *------------------------------------------------------------------------* *------------------------------------------------------------------------* A Crytographic Problem May 22, 1994 David J. Snook *------------------------------------------------------------------------* There has been a great deal of media discussion, about Clipper Chips, information privacy, and the "cracking" of RSA-129. This problem is designed around the underlying mathematics of modern crytographic systems: RSA, in this particular case. (Rivest, Shamir, Adleman) The security of these systems is based on the fact that very large numbers (200 digits) are very difficult and time consuming to factor. The numbers associated with this problem are very small, in crytographic terms, and therefore provide little or no security from the amateur crypt-analyst. In fact, this problem can be solved with paper, pencil and a "cheap" scientific calculator. Below, is a line of ciphertext, two(2) public keys, followed by the procedures and equations used to encipher and decipher the message. The problem ........ What was the original message? C C C C C C C C 1 2 3 4 5 6 7 8 Ciphertext= 48284 65276 34353 19422 26879 31970 31567 52773 Key #1 N= 83323 Key #2 E= 2683 *--------------------* Procedures & Equations *------------------------------------------------------------------------* N = p*q (p) and (q) both prime PUBLIC Phi(N) = (p-1)(q-1) Totient function (Euler) E = Integer (E)nciphering Key PUBLIC -1 D = E mod Phi(N) (D)eciphering key PRIVATE Enciphering was done, two(2) characters at a time, using the encoding alphabet listed below to form (P)laintext blocks. Each block was then raised to the power of E modulo N to produce the blocks of (C)iphertext. There are eight(8) blocks of (C)iphertext with each containing exactly two(2) characters. E E E C = P mod N , C = P mod N , ........ C = P mod N 1 1 2 2 8 8 Deciphering is accomplished by raising each (C)iphertext block to the power of D modulo N. This recovers the (P)laintext blocks and hence the original message text. D D D P = C mod N , P = C mod N , ........ P = C mod N 1 1 2 2 8 8 *-------------------------------------------------------------------------* *---------------* Encoding alphabet *-------------------------------------------------------------------------* a = 01 b = 02 c = 03 d = 04 e = 05 f = 06 g = 07 h = 08 i = 09 j = 10 k = 11 l = 12 m = 13 n = 14 o = 15 p = 16 q = 17 r = 18 s = 19 t = 20 u = 21 v = 22 w = 23 x = 24 y = 25 z = 26 A = 27 B = 28 C = 29 D = 30 E = 31 F = 32 G = 33 H = 34 I = 35 J = 36 K = 37 L = 38 M = 39 N = 40 O = 41 P = 42 Q = 43 R = 44 S = 45 T = 46 U = 47 V = 48 W = 49 X = 50 Y = 51 Z = 52 0 = 53 1 = 54 2 = 55 3 = 56 4 = 57 5 = 58 6 = 59 7 = 60 8 = 61 9 = 62 = 63 . = 64 , = 65 ; = 66 ? = 67 *-------------------------------------------------------------------------* Plaintext example *---------------* Message = S i r I s a a c N e w t o n Plaintext = 4509 1863 3519 0101 0363 4005 2320 1514 P P P P P P P P ... P 11 12 13 14 15 16 17 18 k *-------------------------------------------------------------------------* -- David J. Snook.................................ua532@freenet.victoria.bc.ca