Thread View: sci.crypt
2 messages
2 total messages
Started by Mr. Lyn R. Kennedy
Thu, 17 Dec 1992 22:09
RSA
Author: Mr. Lyn R. Kennedy
Date: Thu, 17 Dec 1992 22:09
Date: Thu, 17 Dec 1992 22:09
26 lines
1692 bytes
1692 bytes
I haven't seen these items mentioned but I'm not a math whiz so maybe
it's hidden in there somewhere.
You can get an encode/decode pair ( e and d ) by taking d*e mod
(p-1)*(q-1) = 1. This implies that the smallest value for d*e
is ((p-1)*(q-1))+1 but it's actually (((p-1)*(q-1))/2)+1. If fact, d*e
must be some value (((p-1)*(q-1)/2)*x)+1 where x is any integer >0
Also, for ANY value of n ( =p*q), there are at least nine values of m
(the message) that will encrypt as m. I.e. E(m) = m and D(m) = m. Three
of these are trivial, m=0, 1, and n-1. The other six allow factoring n.
For some values of e, there are more cases but I'm not sure how easy it
would be to get the factors knowing one of those. This brings up the
question of whether the proceedure should watch for such cases. Only
while signing a message would the sender be the one to discover key was
compromised. I know it's not at all likely but it seems like it could
cause problems.
-------------------------------------------------------------------------
73, internet | lrk@k5qwb.lonestar.org
Lyn Kennedy packet radio | K5QWB @ N5LDD.#NTX.TX.US.NA
pony express | P.O. Box 5133, Ovilla, TX, USA 75154
-------------- "We have met the enemy and he is us." Pogo --------------
Re: RSA
Author: Cetin Kaya Koc
Date: Fri, 18 Dec 1992 02:16
Date: Fri, 18 Dec 1992 02:16
18 lines
1238 bytes
1238 bytes
In article <226XVB4w164w@k5qwb.lonestar.org> lrk@k5qwb.lonestar.org (Mr. Lyn R. Kennedy) writes: > Also, for ANY value of n ( =p*q), there are at least nine values of m > (the message) that will encrypt as m. I.e. E(m) = m and D(m) = m. Three > of these are trivial, m=0, 1, and n-1. The other six allow factoring n. > For some values of e, there are more cases but I'm not sure how easy it E(m) = m for as many as k messages where k = [1+gcd(e-1,p-1)]*[1+gcd(e-1,q-1)]. The smallest value k=[1+2]*[1+2]=9 as pointed out. This is because gcd(e-1,p-1) >= 2 since p and e are odd numbers; p is prime, and gcd(e,(p-1)(q-1))=1 and thus e is odd. Thus, you want gcd(e-1,p-1) and gcd(e-1,q-1) as small as possible. Ref: Blakley & Borosh. Comp. & Math. with App. 5:169-178, 1979.
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads