Prev: Hash question
Next: A New/Old code Just For Fun
From: Pubkeybreaker on 20 Jul 2010 12:37 On Jul 20, 12:15 pm, Francois Grieu <fgr...(a)gmail.com> wrote: > Le 20/07/2010 16:41, Yehudidedum a écrit : > > > If I wanted to publish the decryption key and keep the encryption > > key private (using something like RSA.) > > The encryption key (private): E = (n,e) > > The decryption key (public): D = (n,d) > > > (This may seem strange) > > I would be able to encrypt messages that anyone with the public > > key could decrypt. > > I could use this as a form of validation, if the decrypted message > > is valid (ie, makes sense in some way) then it could be seen as a > > good , ie from the holder of the encryption key. > > As pointed by Tom St Denis, you are reinventing RSA signature. > > > How difficult would it be to deduce E knowing D. > > Hard, if either > - E is big, random, and secret; > - you make a regular RSA key and permute E and D. This is totally false. Take a typical 1024 bit RSA key with (say) e = 3, 17, 65537, or anything else small. D will be large. If you now swap the role of D and e by publishing D and keeping e secret, then e is very easily deduced by known Lattice Reduction attacks.
From: Francois Grieu on 20 Jul 2010 14:07 Le 20/07/2010 18:37, Pubkeybreaker a �crit : > On Jul 20, 12:15 pm, Francois Grieu <fgr...(a)gmail.com> wrote: >> Le 20/07/2010 16:41, Yehudidedum a �crit : >> >>> If I wanted to publish the decryption key and keep the encryption >>> key private (using something like RSA.) >>> The encryption key (private): E = (n,e) >>> The decryption key (public): D = (n,d) >> >>> (This may seem strange) >>> I would be able to encrypt messages that anyone with the public >>> key could decrypt. >>> I could use this as a form of validation, if the decrypted message >>> is valid (ie, makes sense in some way) then it could be seen as a >>> good , ie from the holder of the encryption key. >> >> As pointed by Tom St Denis, you are reinventing RSA signature. >> >>> How difficult would it be to deduce E knowing D. >> >> Hard, if either >> - E is big, random, and secret; >> - you make a regular RSA key and permute E and D. > > This is totally false. Take a typical 1024 bit RSA key with (say) > e = 3, 17, 65537, or anything else small. D will be large. > > If you now swap the role of D and e by publishing D and keeping e > secret, then e is very easily deduced by known Lattice Reduction > attacks. Indeed; or just by enumeration if e is real small. My idea with "make a regular RSA key and permute E and D" was: - choose e, perhaps small, e.g. 65537 - generate p,q,n,d as usual - set N=n, D=e and E=d - publish (N,D), the O.P. "Decryption key", which is (n,e) - keep (N,E) secret, the O.P "Encryption key", which is (n,d). Francois Grieu
From: unruh on 20 Jul 2010 14:24 On 2010-07-20, Yehudidedum <pete.mcevoy(a)metastate.co.uk> wrote: > If I wanted to publish the decryption key and keep the encryption > key private (using something like RSA.) > The encryption key (private): E = (n,e) > The decryption key (public): D = (n,d) RSA is completely symmetric with respect to encryption and decryption. Unfortunately, the encrytption key e is usually chosen to make encryption easy (2^n+1) and thus it is terribly easy to guess, making the scheme pretty useless for encryption. > > (This may seem strange) > I would be able to encrypt messages that anyone with the public > key could decrypt. That is called signing. > I could use this as a form of validation, if the decrypted message > is valid (ie, makes sense in some way) then it could be seen as a > good , ie from the holder of the encryption key. That is called signing. > > How difficult would it be to deduce E knowing D. IF D is chosen randomly, very very hard. If e is chosen in the usual way, very very easy. > > I do know that you can use RSA to generate a digital signature > the reason I am asking is that these seem to be quite large > about 320 bits for RSA(1024).and my messages have to > be very short - less than 50 bytes in general. The signature has to be at least the size of the key (1024 bits). You cannot encrypt or sign reliably with RSA with such a short message. 400 bits is breakable. > > Thanks for any help. > Y
From: unruh on 20 Jul 2010 14:28 On 2010-07-20, Pubkeybreaker <pubkeybreaker(a)aol.com> wrote: > On Jul 20, 12:15?pm, Francois Grieu <fgr...(a)gmail.com> wrote: >> Le 20/07/2010 16:41, Yehudidedum a ?crit : >> >> > If I wanted to publish the decryption key and keep the encryption >> > key private (using something like RSA.) >> > The encryption key (private): E ?= (n,e) >> > The decryption key (public): D ?= (n,d) >> >> > (This may seem strange) >> > I would be able to encrypt messages that anyone with the public >> > key could decrypt. >> > I could use this as a form of validation, if the decrypted message >> > is valid (ie, makes sense in some way) then it could be seen as a >> > good , ie from the holder of the encryption key. >> >> As pointed by Tom St Denis, you are reinventing RSA signature. >> >> > How difficult would it be to deduce E knowing D. >> >> Hard, if either >> - E is big, random, and secret; >> - you make a regular RSA key and permute E and D. > > This is totally false. Take a typical 1024 bit RSA key with (say) > e = 3, 17, 65537, or anything else small. D will be large. > > If you now swap the role of D and e by publishing D and keeping e > secret, then e is very easily deduced by known Lattice Reduction > attacks. You misunderstood. He wants to choose e as usual, and then swap e and d, and then follow the OP suggestion and publish the new d (which is the old d). Ie, the two swaps cancel and you have back the original scheme. It was a joke. >
From: Yehudidedum on 23 Jul 2010 10:33
Many thanks for the replies, they have been helpful. The problem I have is getting validation into a very small message. (It is a similar problem to the Tachograph Smart Cards mention by Francious Grieu.) "schemes with message recovery" may be useful if I need more payload. At the moment it looks like my ECDSA may be small enough. ECDSA with a key size of 160 bits, produces a digital signature of r,s, each of which is 160 bits long so a total of 320. I now also realize that my original post may have looked a little like a joke. It was not intentional, only caused by my own ignorance of how DSA works. [quote]about 320 bits for RSA(1024).[/quote] I got the original estimates of signature size from: http://en.wikipedia.org/wiki/Elliptic_Curve_DSA#Key_and_signature_size_comparison_to_DSA which seemed to imply to me that, 4t = 320 was the size for both RSA1024 & EC160. I had also found this somewhere on the NISTsite, but I've lost the url and I can't seem to resurf that) Anyway, many thanks. Y |