Re: Actual difference between RSA public and private keys?
From: Michael Amling (nospam_at_nospam.com)
Date: 04/04/05
- Next message: Tom St Denis: "Re: Actual difference between RSA public and private keys?"
- Previous message: Justin: "Re: Surrogate Factoring Theorem"
- In reply to: Valery Pryamikov: "Re: Actual difference between RSA public and private keys?"
- Next in thread: Valery Pryamikov: "Re: Actual difference between RSA public and private keys?"
- Reply: Valery Pryamikov: "Re: Actual difference between RSA public and private keys?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Mon, 04 Apr 2005 03:00:41 GMT
Valery Pryamikov wrote:
> "Michael Amling" <nospam@nospam.com> wrote in message
> news:JRE3e.28492$hU7.1167@newssvr33.news.prodigy.com...
>>
>> If the modulus is n bits, then the probability of lg(d)<n/2 when e
>> is selected randomly is roughly 2**(n/2-lg(lcm(p-1,q-1))), right?
>
> not quite - if n is modulus, gcd(e, phi(n)) = 1
This is true.
> and e*d = 1 mod phi(n)
This is not necessarily true. e*d==1 mod lcm(p-1,q-1) is a necessary
and sufficient condition for RSA key pair exponents. e*d==1 mod phi(n)
is not a necessary condition.
> then ceiling(log(e))+ceiling(log(d)) ~= ceiling(log(phi(n))) =<
> ceiling(log(n)).
> if e is choosen at random from ceiling(log(n)/2) bit numbers - then
Why would you do that? There's no need to limit the length of e to
half the length of n.
What I meant by "e is selected randomly" is that e is selected either
uniformly at random from among all 3..n-1 that are relatively prime to
p-1 and to q-1, or else e is selected uniformly at random from among all
3..lcm(p-1,q-1)-1 that are relatively prime to p-1 and q-1. For such an
e, d mod lcm(p-1,q-1) is practically uniformly distributed among all
3..lcm(p-1,q-1)-1, the exceptions to uniformity being the probability of
2 and 2**-1 mod lcm(p-1,q-1).
> ceiling(log(d)) will be less or equal to ceiling(log(n)/2).
How does lg(d)<=lg(n)/2 follow from lg(e)<lg(n)/2?
> But having a small public exponent guarantees that private exponent will
> be big and not vulnerable to Weiner's attack.
Note: I did not claim that small d is impossible, just of negligible
probability for reasonable n.
Say lg(n)=1024, lg(gcd(p-1,q-1))<200, then
lg(lcm(p-1,q-1))>=1024-200=824. A d selected from a uniform distribution
on 1..2**824 has a probability of being <2**512 of less than 2**-312,
which we all regard as negligible.
The probability of a d selected from a uniform distribution on all
3..lcm(p-1,q-1)-1 that are relatively prime to p-1 and q-1 being <2**512
should also be close to 2**-312 and certainly negligible.
Maybe I haven't understood what you meant.
--Mike Amling
- Next message: Tom St Denis: "Re: Actual difference between RSA public and private keys?"
- Previous message: Justin: "Re: Surrogate Factoring Theorem"
- In reply to: Valery Pryamikov: "Re: Actual difference between RSA public and private keys?"
- Next in thread: Valery Pryamikov: "Re: Actual difference between RSA public and private keys?"
- Reply: Valery Pryamikov: "Re: Actual difference between RSA public and private keys?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
