| |
 |
|
|
Science Forum Index » Cryptography Forum » RSA ecnryption confusion...
Page 3 of 3 Goto page Previous 1, 2, 3
|
| Author |
Message |
| Greg Rose... |
 Posted: Tue May 13, 2008 11:31 am |
|
|
|
Guest
|
In article <YsadnRnRlIuSbrTVRVnyvQA at (no spam) posted.plusnet>,
Blind Anagram <noone at (no spam) nowhere.org> wrote:
Quote: What I am unclear about here is that the two keys (e,N) and (d,N) are
interchangeable at the fundamental algorithm level.
Hence if an algorithm can recover the prime factors of N knowing only d
when d < N^0.29, why cannot this also be done knowing only e when e is
less than N^0.29 (which it pretty well always is)?
Because it is assumed in the former case that you know e too. After all,
it's public.
Greg.
--
Greg Rose
232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au |
|
|
| Back to top |
|
| Peter Fairbrother... |
| Posted: Tue May 13, 2008 2:42 pm |
|
|
|
Guest
|
Pubkeybreaker wrote:
Quote: sigh. I need to bring back my old signature.
The implementation is *irrelevant*. If the private key is known,
then the public key becomes *trivially* constructible. It doesn't
matter if p,q, are stored directly, if they are stored in CRT
format, or even if they are not stored at all. If the private
exponent is KNOWN, then constructing the factors requires a simple,
polynomial time random algorithm. (hint: if the private exponent is
known, then it is some multiple of phi(N))
??
In classical RSA without "optimisations" the private exponent is the
inverse of the public exponent modulo phi(N). It is not a multiple of
phi(N).
If both exponents are long enough (> N^0.29) there is no known
polynomial time algorithm which will find one exponent, given only N and
the other exponent.
-- Peter Fairbrother |
|
|
| Back to top |
|
| Blind Anagram... |
| Posted: Tue May 13, 2008 2:59 pm |
|
|
|
Guest
|
Phil Carmody wrote:
Quote: "Blind Anagram" <me at (no spam) nothere.gov> writes:
"Phil Carmody" <thefatphil_demunged at (no spam) yahoo.co.uk> wrote in message
news:87d4nqmxt6.fsf at (no spam) nonospaz.fatphil.org...
"Blind Anagram" <me at (no spam) nothere.gov> writes:
"Phil Carmody" <thefatphil_demunged at (no spam) yahoo.co.uk> wrote in message
news:87d4nrmly1.fsf at (no spam) nonospaz.fatphil.org...
Blind Anagram <noone at (no spam) nowhere.org> writes:
Pubkeybreaker wrote:
The implementation is *irrelevant*. If the private key is
known, then the public key becomes *trivially* constructible.
It doesn't matter if p,q, are stored directly, if they are
stored in CRT format, or even if they are not stored at all.
If the private exponent is KNOWN, then constructing the
factors requires a simple, polynomial time random algorithm.
When d is less than N^0.29, does the reconstruction of the
factors of N from d work without knowing e?
Yes. If N, e and d are known, factoring N is trivial.
ed is a multiple of lambda(pq), can be used to
reconstruct phi(pq) = pq-p-q+1. Therefore you can
trivially find p+q. 2 equations in 2 unknowns - bingo.
Phil, did you miss the "without knowing e" bit?
No. With knowing e, there's a trivial algorithm as shown.
Therefore the lattice algorithm evidently applies to the
"without knowing e" case. What other case did you think
it applied to?
I was puzzled because most of your answer was about a question that I
did not ask.
Where's the black king? It's not on row 1,2,3,4,5,7, or 8,
and not in column 1,2,3,5,6,7,8.
Once you remove other possibilities, that which is left
is clearly defined.
What I am unclear about here is that the two keys (e,N) and (d,N) are
interchangeable at the fundamental algorithm level.
Hence if an algorithm can recover the prime factors of N knowing only d
when d < N^0.29, why cannot this also be done knowing only e when e is
less than N^0.29 (which it pretty well always is)?
I may well be screwed up here since it is a long time since I really
looked at any of this. But my uncertainty was such that I felt it was
worthwhile posing the question to see what came of it. |
|
|
| Back to top |
|
| Phil Carmody... |
| Posted: Tue May 13, 2008 4:21 pm |
|
|
|
Guest
|
Blind Anagram <noone at (no spam) nowhere.org> writes:
Quote: What I am unclear about here is that the two keys (e,N) and (d,N) are
interchangeable at the fundamental algorithm level.
Hence if an algorithm can recover the prime factors of N knowing only
d when d < N^0.29, why cannot this also be done knowing only e when e
is less than N^0.29 (which it pretty well always is)?
That 'if' is false.
What's closer to the truth (I've not actually read the paper,
so don't take this as gospel) is:
If
modulus N is known (which by standard definitions it is)
public exponent u is known (ditto)
private exponent v is < ~N^0.29
Then
N can be factored
The dependency is upon *both* exponents. It remains true
even if you swap the roles of u and v.
Phil
--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration |
|
|
| Back to top |
|
| Thomas Pornin... |
| Posted: Tue May 13, 2008 4:28 pm |
|
|
|
Guest
|
According to Blind Anagram <noone at (no spam) nowhere.org>:
Quote: What I am unclear about here is that the two keys (e,N) and (d,N) are
interchangeable at the fundamental algorithm level.
At the fundamental algorithm level, there are two exponents which define
two permutations. "Keys" are defined when the core algorithm is
converted into a cryptosystem, either RSA asymmetric encryption or RSA
digital signatures. PKCS#1 defines what keys are.
Now, considering the core algorithm and avoiding terms such as "key"...
It so happens that when you generate n, d and e, you can arrange for
one of the exponents to be "short", i.e. much shorter than the modulus
itself. Basically, you choose one exponent and compute the other from
that (using your knowledge of the modulus factors). Usually, you make
public the short exponent (i.e. you choose "e" to be short).
Now you may encounter a situation where you would like the private
exponent to be short, because the system which will use it is not very
powerful, and short exponents promote faster computing. E.g. you set up
a SSH server on a low-powered embedded system. You are willing to give
the server the easy side, because the client will be an average PC with
50x the computing power of the server.
It turns out that this is a bad idea. I.e., if an attacker knows n and
e, and knows that n and e have been chosen specifically to have a short
d, then the attacker may recover d through lattice reduction (and from d
and e he may factor n). The best known attack works if the length of d
is no more than about 29% of the length of n.
In other words, the attack works only if the attacker knows the modulus
and one exponent, and the other exponent (the "private" one, which the
attacker wishes to recover) is short. It does not work if the short
exponent is the one that the attacker knows already.
Another way to see that is that for a given modulus n, knowing an
exponent which has a short counterpart for that modulus yields some
structural information about the modulus, information which can be used
to factor n.
--Thomas Pornin |
|
|
| Back to top |
|
| Blind Anagram... |
| Posted: Tue May 13, 2008 5:42 pm |
|
|
|
Guest
|
"Phil Carmody" <thefatphil_demunged at (no spam) yahoo.co.uk> wrote in message
news:87d4npkihg.fsf at (no spam) nonospaz.fatphil.org...
Quote: Blind Anagram <noone at (no spam) nowhere.org> writes:
What I am unclear about here is that the two keys (e,N) and (d,N) are
interchangeable at the fundamental algorithm level.
Hence if an algorithm can recover the prime factors of N knowing only
d when d < N^0.29, why cannot this also be done knowing only e when e
is less than N^0.29 (which it pretty well always is)?
That 'if' is false.
But your answer to my earlier question:
"When d is less than N^0.29, does the reconstruction of the factors of N
from d work without knowing e?"
was "Yes", followed by an explanation of how to factor N when both d and e
are known.
I queried whether you had missed my stipulation that 'e' was not known and
you responded with an explantion of how you had deduced that the algorithm
would work without knowing 'e'.
Now you are saying that it _is_ necessary to know e.
Quote: The dependency is upon *both* exponents. It remains true
even if you swap the roles of u and v.
In which case my original question to pubkeybreaker in this sub-thread was
well formed. |
|
|
| Back to top |
|
| Blind Anagram... |
| Posted: Tue May 13, 2008 6:17 pm |
|
|
|
Guest
|
"Thomas Pornin" <pornin at (no spam) bolet.org> wrote in message
news:482a0805$0$11395$426a34cc at (no spam) news.free.fr...
Quote: According to Blind Anagram <noone at (no spam) nowhere.org>:
What I am unclear about here is that the two keys (e,N) and (d,N) are
interchangeable at the fundamental algorithm level.
[snip]
Quote: In other words, the attack works only if the attacker knows the modulus
and one exponent, and the other exponent (the "private" one, which the
attacker wishes to recover) is short. It does not work if the short
exponent is the one that the attacker knows already.
Thank you for this explanation. This aligns with my understanding of the
attack.
Which leaves my original question in this subthread unanswered. |
|
|
| Back to top |
|
| Blind Anagram... |
| Posted: Tue May 13, 2008 6:30 pm |
|
|
|
Guest
|
"Greg Rose" <ggr at (no spam) nope.ucsd.edu> wrote in message
news:g0d1c8$qml$2 at (no spam) ihnp4.ucsd.edu...
Quote: In article <YsadnRnRlIuSbrTVRVnyvQA at (no spam) posted.plusnet>,
Blind Anagram <noone at (no spam) nowhere.org> wrote:
What I am unclear about here is that the two keys (e,N) and (d,N) are
interchangeable at the fundamental algorithm level.
Hence if an algorithm can recover the prime factors of N knowing only d
when d < N^0.29, why cannot this also be done knowing only e when e is
less than N^0.29 (which it pretty well always is)?
Because it is assumed in the former case that you know e too. After all,
it's public.
Normally, yes.
But if you follow this whole thread almost nothing is 'normal' :-(
The post by pubkeybreaker and my original question in response to it are
important in understanding this subthread (I posed the question when 'e' is
not known and not known to be small). |
|
|
| Back to top |
|
| Mark Wooding... |
| Posted: Wed May 14, 2008 5:17 am |
|
|
|
Guest
|
H.K. Kingston-Smith <HKK-S at (no spam) yahoo.com> wrote:
Quote: Is it not the case that both RSA keys can be used for encryption
or decryption? That is, is it not true that something encrypted with a
given RSA private key can only be decrypted with its corresponding
public key, and something encrypted with a given public key can only
be decrypted with its corresponding private key?
It's common, but unfortunate, that introductory texts use the terms
`encryption' and `decryption' for the RSA public- and private-key
operations. These are poor names. RSA on its own (`textbook RSA') is
neither an encryption scheme nor a digital signature scheme. Rather, it
is a `trapdoor one-way permutation family' (`TOWPF'). It is possible to
use a TOWPF as a component in an asymmetric encryption scheme (e.g.,
using OAEP or RSA-KEM in a KEM/DEM construction) or digital signature
scheme (e.g., using PSS), but in and of itself it is neither.
It is just as wrong to speak of `encrypting' with the private key as it
is to speak of `decrypting' with it. Instead, we talk about `applying'
(the public-key operation) and `inverting' (private-key operation) the
permutation.
There's another problem too.
RSA key generation usually works in two stages. In the first stage, one
chooses a pair of large prime numbers p and q, of roughly the same size,
and computes n = p q. (We'll not concern ourselves with this part of
the process, although it's very important in practice.) In the second,
one chooses integers (`exponents') d and e such that
e d == 1 (mod each of p - 1 and q - 1)
This is only possible when both e and d have no factors in common with
either p - 1 or q - 1. If you are given a satisfactory value of e, then
the relationship given above fixes a unique value
0 < d < lcm(p - 1, q - 1)
and vice-versa.
If that were all there was to it, we'd just choose e (or d) uniformly at
random from that interval, and work out the other. It wouldn't matter
which we chose first; the uniform distribution of the other is assured
by the uniqueness property. Therefore we'd have a symmetry: it wouldn't
matter which of e or d we declared to be the public exponent and which
the private. As it happens, e is conventionally the public exponent and
d is the private exponent.
But that's not all there is to it: there are (major) performance
effects. RSA goes faster when the exponents are small. Unfortunately
RSA is insecure if d is small. No significant vulnerabilities[1] are
known for small e (well, e >= 3; otherwise d = e = 1 and you lose). So
what we actually do is choose some small e, maybe 3, or (popularly)
65537, and then work out what d is as a result. (This actually forces d
to be fairly large -- plenty large enough to avoid the insecurity
described above.) Fortunately, the private-key holder has some other
tricks he can use to make RSA go faster: these tricks are not available
to others who only have the public key.
Anyway, the punchline is that, although the theoretical description of
RSA doesn't distinguish between the `public' and `private' exponents,
there is a significant practical difference between the two.
[1] You lose if e is small and you encrypt e identically-padded messages
for different people. But, as mentioned, RSA isn't an encryption
scheme, and a real encryption scheme just won't let you do this.
(Technically, this property doesn't prevent RSA from being a TOWPF,
and so encryption and signature schemes built on TOWPFs must be able
to cope despite this apparent weakness.)
You also lose if m^e < n; but this happens with negligible
probability when m is chosen randomly from 0, 1, ..., n - 1. Again,
a high-level scheme has to be able to deal with this, so it's not a
practical problem.
-- [mdw] |
|
|
| Back to top |
|
| Phil Carmody... |
| Posted: Wed May 14, 2008 7:51 am |
|
|
|
Guest
|
"Blind Anagram" <me at (no spam) nothere.gov> writes:
Quote: "Phil Carmody" <thefatphil_demunged at (no spam) yahoo.co.uk> wrote in message
news:87d4npkihg.fsf at (no spam) nonospaz.fatphil.org...
Blind Anagram <noone at (no spam) nowhere.org> writes:
What I am unclear about here is that the two keys (e,N) and (d,N) are
interchangeable at the fundamental algorithm level.
Hence if an algorithm can recover the prime factors of N knowing only
d when d < N^0.29, why cannot this also be done knowing only e when e
is less than N^0.29 (which it pretty well always is)?
That 'if' is false.
But your answer to my earlier question:
"When d is less than N^0.29, does the reconstruction of the factors of
N from d work without knowing e?"
was "Yes", followed by an explanation of how to factor N when both d
and e are known.
I queried whether you had missed my stipulation that 'e' was not known
and you responded with an explantion of how you had deduced that the
algorithm would work without knowing 'e'.
Now you are saying that it _is_ necessary to know e.
Aha, I did misread your question, just not the way that
you imagined. I thought it began "When e is less than ...".
When d is known (your "from d"), it matters not what its
magnitude is, so I just mapped the comparison onto being
about e instead. Sorry.
Phil
--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration |
|
|
| Back to top |
|
| |
Page 3 of 3 Goto page Previous 1, 2, 3
All times are GMT - 5 Hours
The time now is Sun Jul 27, 2008 2:45 am
|
|
