[pycrypto] _RSA.py and generate_py

Anthony Honstain honstain at gmail.com
Mon Nov 2 00:03:30 CST 2009


It is essentially the same as the patch I implemented, I have attached an
attempt to prove (the best I can do quickly) that this check is sufficient
to guarantee that GCD(e, (p-1)(q-1))=1. It did not seem
immediately intuitive to me so I tried to prove it.

Thanks!
Anthony Honstain

On Sun, Nov 1, 2009 at 5:04 PM, Dwayne C. Litzenberger <dlitz at dlitz.net>wrote:

> On Mon, Aug 03, 2009 at 09:41:50PM -0400, Dwayne C. Litzenberger wrote:
>
>> On Wed, May 27, 2009 at 09:50:07PM -0700, Anthony Honstain wrote:
>>
>>> In the generate_py function of lib/Crypto/PublicKey/_RSA.py , it would
>>> appear to be possible that the the primes p and q can be generated such
>>> that
>>> the GCD( 65537, (p-1)(q-1)) != 1 which would result in a unusable key. If
>>> anyone can clarify this it would be greatly appreciated.
>>>
>>
>> I haven't looked into this claim yet, but I've filed a bug report:
>>
>>    https://bugs.launchpad.net/pycrypto/+bug/408660
>>
>
> Lorenz Quack has posted a patch that he says will solve this problem.  It
> checks that e does not divide p-1 or q-1.
>
> That should fix this bug, right?
>
>
> --
> Dwayne C. Litzenberger <dlitz at dlitz.net>
>  Key-signing key   - 19E1 1FE8 B3CF F273 ED17  4A24 928C EC13 39C2 5CF7
>  Annual key (2009) - C805 1746 397B 0202 2758  2821 58E0 894B 81D2 582E
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.dlitz.net/pipermail/pycrypto/attachments/20091102/d52ebd8e/attachment.htm 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: GCDproof.pdf
Type: application/pdf
Size: 183722 bytes
Desc: not available
Url : http://lists.dlitz.net/pipermail/pycrypto/attachments/20091102/d52ebd8e/attachment.pdf 


More information about the pycrypto mailing list