[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Crytography - Solution (long) (fwd)
Forwarded message:
From [email protected] Mon Jun 13 12:14:22 1994
Apparently-To: [email protected], [email protected],
[email protected], [email protected],
[email protected]
Message-Id: <[email protected]>
Date: Mon, 13 Jun 94 09:51 PDT
Sender: [email protected] (Benjie KE6BCU)
From: [email protected] (David Snook)
Reply-To: [email protected]
Subject: Crytography - Solution (long)
Designated-To: Internet Amateur Mathematics Society
Replied-From: Internet Amateur Mathematics Society
Precedence: bulk
Sender: [email protected] (Internet Amateur Mathematics Society)
X-Info: email to [email protected] with "FAQ iams" in the message
X-Ignore: iams Ignore this line. It's a mailing-list-loop detector.
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