[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: RSA != RSA?

If I recall correctly, the number of possilble keys is dependent on
the factorization of (p-1)(q-1).  Namely, the more factors you have,
the greater the number of possible keys.  (Note: I might have the
wrong number being factored -- we discussed this in class about 7
years ago and I'm nowhere near my class notes ;)

But basically, IIRC, if you choose p and q as strong primes, such that
both (p-1)/2 and (q-1)/2 are prime, then you will minimize the number
of potential decryption keys to 2.

As a simple example, take p=7,q=5, N=35. You can choose, e.g. e=5, as
5 is relatively prime to (p-1)(q-1) = (6*4) = 24.  You can then show
that either d=11 or d=23 will work to decrypt a message:

	m=5
	c = m^e mod n = 5^5 mod 35 = 10
	m = c^d mod n = 10^11 mod 35 = 5
	              = 10^23 mod 35 = 5

Enjoy,

-derek

Chris Trobridge <CTrobridge@baltimore.com> writes:

> Any idea how many? (just for academic interest)
> 
> Chris
> 
> > -----Original Message-----
> > From: Derek Atkins [mailto:warlord@mit.edu]
> > Sent: 08 February 2001 22:57
> > To: Henry Spencer
> > Cc: IP Security List
> > Subject: Re: RSA != RSA?
> > 
> > 
> > Basically there are multiple decryption keys, d, that are valid for
> > any particular encryption key, e, mod N.  I believe the lcm(p-1,q-1)
> > will force you to generate necessarily one of the multiple d keys.
> > 
> > -derek
> 
> 
> -----------------------------------------------------------------------------------------------------------------
> The information contained in this message is confidential and is intended 
> for the addressee(s) only.  If you have received this message in error or 
> there are any problems please notify the originator immediately.  The 
> unauthorized use, disclosure, copying or alteration of this message is 
> strictly forbidden. Baltimore Technologies plc will not be liable for direct, 
> special, indirect or consequential damages arising from alteration of the 
> contents of this message by a third party or as a result of any virus being 
> passed on.
> 
> In addition, certain Marketing collateral may be added from time to time to 
> promote Baltimore Technologies products, services, Global e-Security or 
> appearance at trade shows and conferences.
>  
> This footnote confirms that this email message has been swept by 
> Baltimore MIMEsweeper for Content Security threats, including
> computer viruses.

-- 
       Derek Atkins, SB '93 MIT EE, SM '95 MIT Media Laboratory
       Member, MIT Student Information Processing Board  (SIPB)
       URL: http://web.mit.edu/warlord/    PP-ASEL-IA     N1NWH
       warlord@MIT.EDU                        PGP key available
References: