[iwar] RSA cracked - NOT!!!


From: Fred Cohen
To: Information Warfare Mailing List
From: fc@all.net
To: iwar@onelist.com

Mon, 5 Feb 2001 22:36:33 -0800 (PST)


fc  Mon Feb  5 22:37:07 2001
Received: from 207.222.214.225
	by localhost with POP3 (fetchmail-5.1.0)
	for fc@localhost (single-drop); Mon, 05 Feb 2001 22:37:07 -0800 (PST)
Received: by multi33.netcomi.com for fc
 (with Netcom Interactive pop3d (v1.21.1 1998/05/07) Tue Feb  6 06:37:01 2001)
X-From_: fc@all.net  Tue Feb  6 00:36:35 2001
Received: from hj.egroups.com (hj.egroups.com [208.50.99.212])
	by multi33.netcomi.com (8.9.3/8.9.3) with SMTP id AAA28520
	for ; Tue, 6 Feb 2001 00:36:33 -0600
X-eGroups-Return: sentto-279987-910-981441396-fc=all.net@returns.onelist.com
Received: from [10.1.4.55] by hj.egroups.com with NNFMP; 06 Feb 2001 06:36:37 -0000
X-Sender: fc@all.net
X-Apparently-To: iwar@onelist.com
Received: (EGP: mail-7_0_2_1); 6 Feb 2001 06:36:35 -0000
Received: (qmail 43070 invoked from network); 6 Feb 2001 06:36:35 -0000
Received: from unknown (10.1.10.26) by l9.egroups.com with QMQP; 6 Feb 2001 06:36:35 -0000
Received: from unknown (HELO all.net) (65.0.156.78) by mta1 with SMTP; 6 Feb 2001 06:36:34 -0000
Received: (from fc@localhost) by all.net (8.9.3/8.7.3) id WAA03504 for iwar@onelist.com; Mon, 5 Feb 2001 22:36:33 -0800
Message-Id: <200102060636.WAA03504@all.net>
To: iwar@onelist.com (Information Warfare Mailing List)
Organization: I'm not allowed to say
X-Mailer: don't even ask
X-Mailer: ELM [version 2.5 PL1]
From: Fred Cohen 
MIME-Version: 1.0
Mailing-List: list iwar@yahoogroups.com; contact iwar-owner@yahoogroups.com
Delivered-To: mailing list iwar@yahoogroups.com
Precedence: bulk
List-Unsubscribe: 
Date: Mon, 5 Feb 2001 22:36:33 -0800 (PST)
Reply-To: iwar@yahoogroups.com
Subject: [iwar] RSA cracked - NOT!!!
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit

From:	http://www.seedmuse.com/rsa_edit.htm

Ted Byfield wrote: 

Subject:   [IRR] RIP RSA 
Date:   Sun, 4 Feb 2001 17:53:12 -0500 
From:   t byfield  
To:   TBTF irregulars 

maybe. 

==================== 

Innocent readers: 

First, apologies (if needed) to the authors and those in the chain of
possession.  The e-mail arrived rather poorly formatted, so I've put it
out here for the TBTF Irregulars to review.  Credit to Leo de Velez, Ron
Rivest, Marc Branchaud, and Barry for bringing the material together. 

Any errors in transcription are mine.  (Although any errors in shift
register theory are not :-)

Gary Stock 
gstock at seedmuse dot com 

==================== 

IRREGULARS: 

I've made an attempt at deconstructing the text Ted Byfield forwarded,
strictly for ease of reading.  It's always difficult following a forward
of a forward of a...  and a series of proofs and analyses in such a
strange order is wacky. 

I'd appreciate anyone taking a peek for corrections needed in the order
of items [A] thru [K].  Also, if you see a structure that seems easier
to read with different spacing, let me know.  I'll clean it up for all
to see. 

This page is http://www.seedmuse.com/rsa_edit.htm

Thanks,

GS

[Update: Mon 01/02/05 13:30 -0500] I believe I've corrected the format
of the table at the end of message [K].  The 72-char wrap/conversion of
tabs/heehaw thang was causing me a little grief last night. 
...

Dear Ron Rivest, 

 Thank you for your reply. 

The first and second equations are similar to the equation used to
calculate the secret key d from e and (p-1)(q-1).  One difference is
they do not need (p-1)(q-1). 

And the third equation is a simple z= y/x, where z is the secret code. 
BUT z is not necessarily equal to d.  This means secret codes are not
unique. 

I'm only using a pentium 100 laptop and an excel software to decipher
secret key of N (value only up to 10^8).  Its fast and instant. 

Best regards, Leo de Velez 

...
From: Ron Rivest  
 Date: Wed, 31 Jan 2001 00:49:09 -0500 
 Subject: [leo@teammail.com: Re: [leo@teammail.com: new way to decrypt RSA code]] 

I don't understand your explanation at all. What is y? What is x? 

Maybe you could explain how it works on the following example? n = 55 e
= 3 ciphertext = 2

Thanks... 

Thanks, Ron Rivest

...
Date: Sat, 03 Feb 2001 12:07:59 +0800 
 From: "leo"  
 To: "Ron Rivest"  
 Subject: new way to decrypt RSA 

 Dear Ron, 

 The solution to 2^D = 1 mod N 

 There are two approaches that I am looking at. 

 The first is to multiply the binary code of N with another number so that the result will all be binary 1.
 This means adding the binary code of N while shifting to the left. This will give a number and add 1 will
 give a power of 2 (log base 2 is discrete). The discrete log is a factor of (p-1)(q-1). At least one half,
 usually one forth, one sixth, or one eighth of (p1-)(q-1). 

 For N=55 = 110111 Multiple = 19065 = 100101001111001 

 Although the operation is simple and fast (add and shift), the number of operation is in the order of 2^N / 5
 . The operation is also not easy to distribute. 

 Another approach is to use the log N base 2. 


 Using Nroot = [sqr(int(sqrtN))] and Ndelta = [N-sqr(int(sqrtN))] and L = int(LOG(N,2)) 

 i=1 
   Starting point X = Nroot - i * Ndelta j = 0 to Ndelta/LOG(N,2) Y = X + j * L 
   Calculate Z = LOG((MOD((2^Y),N),2) 
   If Z is discrete, the D = Y - Z (check 2^D = 1 mod N) 

 i=2 (another computer doing this) 
   Starting point X = Nroot - i * Ndelta j = 0 to Ndelta/LOG(N,2) Y = X + j * L 
   Calculate Z = LOG((MOD((2^Y),N),2) 
   If Z is discrete, the D = Y - Z (check 2^D = 1 mod N) 

 i= up to int(N/Ndelta) (another computer doing this) 
   Starting point X = Nroot - i * Ndelta j = 0 to Ndelta/LOG(N,2) Y = X + j * L 
   Calculate Z = LOG((MOD((2^Y),N),2) 
   If Z is discrete, the D = Y - Z (check 2^D = 1 mod N) 

 I would appreciate if you can share with me a faster way of finding 2^D = 1 mod N 

 Best regards, Leo 

...

 =====[H]===== 
 ============================================================================== 
 To: Ron Rivest  
 From: Leo de Velez  
 Subject: Re: "RSA Broken" ?? 
 Reply-To: leo@teammail.com 
 CC: leo@lessonsplus.com 
 Date: Sat, 3 Feb 2001 16:16:42 +0800 

 Dear Ron, 

I was surprised by the article because my agreement with Edu Lopez over
the phone was that I will email him the explanation after i discuss the
findings with you.  Anyway, without the knowledge of this press report,
I sent you this morning the approach that I am looking at. 
...

Ron Rivest wrote: 

 Dear Leo -- 

Thanks for the more detailed explanation of your approach to attacking
RSA given in your emails (copied below).  For the reasons I will
explain, and as you are perhaps aware, I think your approach is unlikely
to work in practice against large RSA numbers.  It would be very
premature or misleading to characterize RSA as "broken" based on your
work to date. 

...

and so on...

FC
--
Fred Cohen at Sandia National Laboratories at tel:925-294-2087 fax:925-294-1225
  Fred Cohen & Associates: http://all.net - fc@all.net - tel/fax:925-454-0171
      Fred Cohen - Practitioner in Residence - The University of New Haven
   This communication is confidential to the parties it is intended to serve.
	PGP keys: https://all.net/pgpkeys.html - Have a great day!!!

------------------------ Yahoo! Groups Sponsor ---------------------~-~>
eGroups is now Yahoo! Groups
Click here for more details
http://click.egroups.com/1/11231/1/_/595019/_/981441396/
---------------------------------------------------------------------_->

------------------
http://all.net/