RSA attack : will this actually work?

3 views
Skip to first unread message

Bob Silverman

unread,
Jan 15, 1996, 3:00:00 AM1/15/96
to
In article <x.200.3...@x.net>, x <x...@x.net> wrote:
>Found this on talk.politics.guns, but not on sci.crypt. It describes a
>known-plaintext attack on the RSA algorithm.
>Question for the cypher-gods: might it work?
>

No.


stuff deleted.....

> My opinion has been that public key cryptography
>
> 1 is difficult to properly implement,

Why do you say this? Once one has a set of multi-precision routines the implementation
is not that hard, IMO.

> 2 is slow,

RSA is slow. Methods based on discrete logs over GF(2^n) or over Elliptic Curves
are much faster.

> 3 may have been broken or may be broken in the future
> without factoring.

But this says nothing at all! Almost anything not scientifically impossible
"may" happen. It is possible that all of todays codes may be broken in the future.
I ask: so what?

> Consequences of easily breaking public key cryptography could
> prove serious. "A catastrophe!", to quote Hans Buehler.

It would be a big problem; there is no doubt about that.

> Pretty Good Privacy (PGP) is based on RSA.
>
> Should this project succeed, then the code breaker might wish to

I assume by "this project" what is meant is the poster's attempt to break RSA.

> keep results SECRET and decipher PGP-encrypted messages for
> money.

That is a possibility.....

> But this venture sounds risky, however. A safety risk.
>

What would be risky about it? There is no law about decoding stuff brought
to you by others. Unless you know or have reason to believe that obtaining
the ciphertext was illegal in some way.

> If this project succeeds, then NSA will have to recall all of its
> STU-III secure telephones and fax machines. And the U.S. nuclear

The DOD does not use public key methods.

> About 2,300 year old middle east math is especially slippery.
>
> NSA bases most of its cryptographic algorithms on complication.
>

What do you mean by "complication". What has "2300 year old ...math" to do
with anything? What do you mean by slippery? Please elucidate.

> Cryptographic algorithms based on complication suffer

Please explain what you mean by "based on complication".

> deficiencies. Some deficiencies include,
>
> 1 hard to analyze using mathematics,

Why?

> 2 slow,

Please substantiate.

> 3 too much hardware if implemented in hardware.

DES does not take much hardware at all, for example.

> NSA usually insists on hardware implementation.

With good reason.

> Additional NSA algorithm deficiencies are enumerated in the
> Sandia National Laboratories report,

I am astonished that Sandia would publish something which revealed a
weakness in NSA codes, since the NSA does not reveal the codes in the first
place!

> Crypto algorithms based on complication also make it difficult to
> detect whether the crypto key is embedded in the cipher text.

Why is this a problem?
--
Bob Silverman
The MathWorks Inc.
24 Prime Park Way
Natick, MA

Paul Rubin

unread,
Jan 15, 1996, 3:00:00 AM1/15/96
to
In article <4de5tt$e...@puff.mathworks.com>,

Bob Silverman <bo...@mathworks.com> wrote:
>> If this project succeeds, then NSA will have to recall all of its
>> STU-III secure telephones and fax machines. And the U.S. nuclear
>
>The DOD does not use public key methods.

Actually the STU-III apparently uses public key. See W. Diffie,
"The First Ten Years of Public-Key Cryptography" (in G. Simmons'
collection "Contemporary Cryptology") for some info.

Re Payne's "attack" on RSA, Burt Kaliski posted a message about a year
ago explaining the flaw in it. Basically the attack "works" (i.e. it
reveals the secret message if you run the algorithm to completion), but
it takes longer to run than factoring the modulus by brute force would
take.

x

unread,
Jan 15, 1996, 3:00:00 AM1/15/96
to
Found this on talk.politics.guns, but not on sci.crypt. It describes a
known-plaintext attack on the RSA algorithm.
Question for the cypher-gods: might it work?

-------------------------[ begin rsa2.txt ]-------------------------

Adios, Sayonara, Goodbye Public Key Cryptography?

Bill Payne
POB 14838
Albuquerque, NM 87191 USA
505-292-7037
whp...@abq-ros.com [closed]

Copyright 1995 by William H. Payne

Abstract

Decryption exponent is implicitly contained in the encryption
exponent in public key (RSA) cryptography. Encryption, then
decryption, of carefully selected valid irrational algebraic
messages yields the decryption exponent bit by bit. From the
least significant to most significant bit.

Exposing flaws in linear congruential pseudorandom number
generators with simultaneous introduction of revolutionary new
matrix shift register pseudorandom number technology could be
profitable.

Revision Date Reason

0 H 8/17/95 Initial draft.

M 8/28 Continued revision and addition
of text.

T 8/29 Change "invalid" to "valid" in
abstract. Add (m+1)^k == 1 mod m.

M 9/4 Explain multiple solutions to
Euclid's algorithm

U 9/17 Complete 9/4 task, correct several
typos, and truncate file.

M 9/18 Moved description to example,
expanded epilog, and further
truncated file.

T 9/19 Correct date, spacing, ommissions,
and make several minor modifications.

W 1/10/96 Explain MSA cryptoalgorithm
approach. Edit. Correct typos.


Introduction

Simplest form of public key (RSA = Rivest, Shamir, and Adelman)
is computation of

p^e == c mod m

where == means "is congruent to" and m is the congruence modulus.

Caret, ^, denotes exponentiation.

For example,

7 == 1 mod 3 or 7 = 2x3 + 1.

The plaintext message p must be selected relatively prime to the
modulus. Otherwise, the plaintext message may not be recovered
from the ciphertext message, c.

Decryption is accomplished by,

c^d == p mod m.

where d is the decryption exponent.

But there are several conditions which must be met before this
works properly.

The encryption and decryption exponents must obey the
relationship

e x d == 1 mod [ Phi (m)]

where Phi (m) is Euler's totient function (circa 1750).

Most public key implementations select m as the product of two
large prime numbers, say a and b,

m = a x b.

Euler's Phi (totient) function of two prime numbers is

Phi (m) = Phi (a x b) = Phi (a) x Phi (b)= [a-1] x [b-1].

Euler's totient function is the number of numbers less than an
relative prime to m.

An example, using the sieve of Erathosthenes, for the two prime
number 5 and 7 is

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

26 27 28 29 30 31 32 33 34.

Cross out every multiple of five. # under the number indicates
five has been crossed out.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
# # # # #
26 27 28 29 30 31 32 33 34.
#

Now cross out every multiple of 7. $ under the number indicates
a seven is crossed out.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
# $ # $ # # $ #
26 27 28 29 30 31 32 33 34.
$ #

And clearly, since ten numbers were crossed of the 34, were
crossed out,

Phi [35] = Phi [5 x 7] = Phi [5] x Phi [7] = [5-1] x [7-1]
= 24.

So any encryption exponent, e, and decryption exponent, d, must
obey the congruence,

e x d == 1 mod[24]

in this example.

The only possible valid encryption exponents must be relatively
prime to Phi [24], of Phi [Phi [m]], since by Euclid's algorithm
can only have a solution if the encryption exponent and 24 are
relative prime. The factors of 24 are 2x2x2x3. Phi (p^n) =
p^[n-1] x Phi [p]

The sieve of Eratosthenes can be used to verify the correctness
of Euler's totient function.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Multiples of two are first crossed out.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
# # # # # # # # # # #

Then mulitples of three.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
# # # # # # # # # # #
$ $ $ $ $ $ $

so only 1, 5, 7, 11, 13, 17, 19, 23, eight candidates for an
encryption exponent remain. Evaluation of Euler's totient
function gives

Phi [24] = Phi [2^3 x 3] = 2^2 x Phi [2] x Phi [3] = 8

which is verified by the sieving process.

Since public key encryption relies on preliminary multiplication
of two large primes, then Euler's totient function is, therefore
even. Actually, two factors of 2. Phi [p x q] = (p-1) x (q-1)
for p and q prime.

Therefore, any encryption or decryption expontent must, of
course, be odd.

Euclid, in about 300 B.C., observed that if two numbers had a
common factor, then the common factor divided the sum and
difference of the two numbers.

"The Euclidean algorithm: Any two non-zero integers have a
positive greatest common divisor."

If d is relatively prime to a and b [d = (a,b)], then there
exist integers m and n such that d = ma + nb."

Higher Alegbra by Marie Weiss, John Wiley, 1949, sixth printing,
1957, pages 13, 14.

Six, 2x3, and thirty-five, 5x7, both are composite numbers. But
the greatest common division of the two is one. Therefore 6 and
35 are relatively prime.

5x5 = 25 and 25 == 1 mod 24 is obvious but a formal solution is to
choose e = 5. Then

d x 5 + n x 24 = 1

Euclid's algorithm is used to find the solution,

24/5 gives 24 = 4 x 5 + 4

and

5/4 give 5 = 1 x 4 + 1.

Back substitution gives,

1 = 5 - 1 x 4 = 5 -1 x [24 - 4 x 5] = 5 x 5 - 1 x 24

so, using Weiss' symbols,

d =1, a =5 and b=24, then m=5 and n=-1.

Solutions found by Euclid's algorithm are not unique. Multiples
of 5 and 24, in this example, lead to other solutions.

For example,

9 x 5 + l = 46 so 9 x 5 - 46 = -1.

Substitute the left expression for -l,

1 = 5 x 5 + ( 9 x 5 - 46) x 24

= 5 x 221 - 46 x 24.

See Weiss, exercises 1 and 2, page 15.

Using symbols for the public key encryption/decryption example

e = 5 and d = 5.

Suppose the message, which must be relatively prime to the
modulus in this example, 35, is 4.

4^5 = 4x4x4x4x4 = 64x4x4 == 29x4x4 = 116x4 == 11x4 = 9 mod 35.

The ciphertext is 9.

The decryption is

9^5 = 9x9x9x9x9 = 81x9x9x9 == 11x9x9x9 = 99x9x9 == 29x9x9

= 261x9 == 16x9 = 144 == 4 mod 35.

So the plaintext was recovered from the ciphertext.

These computation MAY fail if the plaintext message is not
relatively prime to the modulus.

5^5 mod 35 == 10 mod 35 10^5 == 5 mod 35

15^5 == 15 mod 35

20^5 == 20 mod 35

25^5 == 30 mod 35

But in this example all not-relatively-prime messages are
recovered.

But if any of the intermediate modular computation is zero, then
the modular product remains zero.

Exponentiation Computations

m to the e power is computed

m^e = m^[e0+e1 x 2+e2 x 2^2+e3 x 2^3+e4 x 2^4+ ....]

where e0, e1, e2, e3, ... is the binary expansion of decimal
number e:

e = e0 + e1x2 + e2 x 2^2 + e3 x 2^3 + ...

Then,

m^e = m^e0 x [m^2]^e1 x [m^4]^e2 x [m^8]^e3x ...

This is all reduced modulo the modulus for public key
computations.

The decryption exponent is applied to m^e to retrieve the
plaintext.

m = [m^e]^d
= [m^e0 x [m^2]^e1 x [m^4]^e2 x [m^8]^e3 x ...]^d0 x
[m^e0 x [m^2]^e1 x [m^4]^e2 x [m^8]^e3 x ...]^(2 x d1) x
[m^e0 x [m^2]^e1 x [m^4]^e2 x [m^8]^e3 x ...]^(4 x d2) x
[m^e0 x [m^2]^e1 x [m^4]^e2 x [m^8]^e3 x ...]^(8 x d3) x...

= [m^e0 x [m^2]^e1 x [m^4]^e2 x [m^8]^e3 x ...]^d0 x
[[m^2]^e0 x [m^4]^e1 x [m^8]^e2 x [m^16]^e 3 x ...]^d1 x
[[m^4]^e0 x [m^8]^e1 x [m^16]^e2 x [m^32]^e 3 x ...]^d2 x
[[m^8]^e0 x [m^16]^e1 x [m^32]^e2 x [m^64]^e 3 x ...]^d3 x...

This is shown without reducing the computation with intermediate
modular arithmetic.

For decryption:

1 The message, m, is only possibly raised to one odd
power: m^1.

2 The message is subsequently possibly raised to even
powers.

(m+1)^k mod m

The congruence

(m+1)^k == 1 mod m

is easily verified correct by observing m that = m x 1 + 1 or by
the binomial expansion.

But to make the congruence clear conceptually,

(m+1)^2 = (m+1) x (m+1) == 1 x 1 = 1 mod m

or

(m+1)^2 = m^2+ 2m +1 = 0 + 0 + 1 == 1 mod m

Cipher Text = Plain Text

There exist messages using RSA encryption where the cipher
text is the same as the plain text.

Here is an example for the modulus, m = 35 and the encryption
exponent, e = 5.

The message to be encrypted is 6.

Six is a valid message since 6 is relative prime to 35, (6,35) =
1.

6^5 = 6 x 6^2 x 6^2 = 6 x 36 x 36 == 6 x 1 x 1 == 6 mod 35

Six is, of course, the square root of 36, m+1.

The decription exponent of the message 6 is of the form

6 = 6^d0 x [6^2]^d1 x [6^4]^d2 x [6^8]^d3 x ...

= 6^d0 x 1 x 1 x 1 x mod 36

Therefore, d0 must equal 1 to get the plain text message back
from the ciphertext.

\/\/\/\/\/\/\/\/\/\/\

File truncated at 10:07 Sunday September 17, 1995 and again at
07:03 Monday September 18.

My opinion has been that public key cryptography

1 is difficult to properly implement,

2 is slow,


3 may have been broken or may be broken in the future
without factoring.

Consequences of easily breaking public key cryptography could


prove serious. "A catastrophe!", to quote Hans Buehler.

Pretty Good Privacy (PGP) is based on RSA.

Should this project succeed, then the code breaker might wish to

keep results SECRET and decipher PGP-encrypted messages for
money.

But this venture sounds risky, however. A safety risk.

If this project succeeds, then NSA will have to recall all of its


STU-III secure telephones and fax machines. And the U.S. nuclear

arsenal! But I was told the arsenal was already being fixed.

I used Weiss' book for my first course in higher algebra during
the summer session at the University of Colorado, 1958.

Aboulghassem Zirakzahdeh was our instructor. Zirakzahdeh was a
CU mathematics graduate student at that time, I believe.

"The Encryption Wars: Is Privacy Good or Bad?

Computers: The government says encoding your e-mail
could threaten national security" ...

"Slippery math: The second way the government deals
with crypto is the continued use of its export policy,
which regards encryption technologies as a munition;
like Stinger missiles or plutonium, it cannot be sent
overseas without a license. The difference, of course,
is that the basis of cryptography is mathematics,
something more slippery to contain than bombs or
F-16's. ..."

[Newsweek, April 24, 1995, page 56, by Steven Levy]

About 2,300 year old middle east math is especially slippery.

NSA bases most of its cryptographic algorithms on complication.

Cryptographic algorithms based on complication suffer
deficiencies. Some deficiencies include,

1 hard to analyze using mathematics,

2 slow,


3 too much hardware if implemented in hardware.

NSA usually insists on hardware implementation.

Additional NSA algorithm deficiencies are enumerated in the
Sandia National Laboratories report,

William H. Payne Data Authentication for the Deployable
Seismic Verification System, SANDIA REPORT,
SAND91-2201*UC-706, 1991.

This unclassified technical report documents the US/USSR
Comprehensive Test Ban Treaty seismic data authenticator I
designed and built.

Crypto algorithms based on complication also make it difficult to
detect whether the crypto key is embedded in the cipher text.

Files code.txt, oleary15.txt, and Swiss Radio International audio
cassette tape contain the "spiked" crypto unit spy bust story.

[write Payne for the cassette tape if interested]

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Colin James III, Principal Scientist cja...@cec-services.com
CEC Services, 2080 Kipling St, Lakewood, CO 80215-1502 USA
Voice: 303.231.9437; Facsimile: .231.9438; Data: .231.9434
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Bruce Schneier

unread,
Jan 15, 1996, 3:00:00 AM1/15/96
to
In article <x.200.3...@x.net>, x <x...@x.net> wrote:
>Found this on talk.politics.guns, but not on sci.crypt. It describes a
>known-plaintext attack on the RSA algorithm.
>Question for the cypher-gods: might it work?
>
>-------------------------[ begin rsa2.txt ]-------------------------
>
> Adios, Sayonara, Goodbye Public Key Cryptography?
>
> Bill Payne

No.

Bruce


Colin Andrew Percival

unread,
Jan 16, 1996, 3:00:00 AM1/16/96
to
Bob Silverman (bo...@mathworks.com) wrote:
: In article <x.200.3...@x.net>, x <x...@x.net> wrote:

: > keep results SECRET and decipher PGP-encrypted messages for
: > money.
:
: That is a possibility.....

: > But this venture sounds risky, however. A safety risk.
: >
:
: What would be risky about it? There is no law about decoding stuff brought


: to you by others. Unless you know or have reason to believe that obtaining
: the ciphertext was illegal in some way.

I think that the poster was (maybe reasonably) paranoid about the NSA
trying to kill anyone who knew how to decode RSA.

Colin Percival


LESLIE MCBRIDE

unread,
Jan 16, 1996, 3:00:00 AM1/16/96
to
x...@x.net (x) wrote:
>Found this on talk.politics.guns, but not on sci.crypt. It describes a
>known-plaintext attack on the RSA algorithm.
>Question for the cypher-gods: might it work?
>
Yes the attack works. However it requires you to use the Sieve of
Erathosthenes for all integers up to 2^512 or more.
That requires an array of that many elements. It is estimated
there are less atoms in the universe than that. What would you
use for the array? This attack basically boils down to factoring
the number and by a slow method at that.
Leslie McBride

Reply all
Reply to author
Forward
0 new messages