[pycrypto] Bug in Crypto.PublicKey.RSA?

Dwayne C. Litzenberger dlitz at dlitz.net
Tue Sep 9 06:24:05 CST 2008

> >>> keysize=368
> >>> privkeyA = RSA.generate(keysize, rpool.get_bytes)
>[ finishes in close to zero time ]
> >>> keysize=369
> >>> privkeyA = RSA.generate(keysize, rpool.get_bytes)
>Hangs forever.... well at least 10's of minutes.

I filed a bug report:


>> I should also add that you should not be encrypting user data directly 
>> using RSA.  You _need_ padding like PKCS#1 if you want any security.
>Hmm, I was not aware of padding issues.  What is the attack?  How much is the 
>ideal padding?  Is the attack related to guessing the plain text based on the 
>file size?  Is the padding supposed to be random extra bytes?  Filled to some 
>boundary like the next 16 bytes?  More?  Does compressing the plain text help?

If you're asking "how much" padding, then you misunderstand what is meant 
by RSA "padding".  It is NOT just a simple matter of appending zeros to a 
message.  Quoting Wikipedia:

     "In public key cryptography, padding is the process of preparing a 
     message for encryption or signing with a primitive such as RSA. A 
     popular example is OAEP. This is called "padding" because originally, 
     random material was simply appended to the message to make it long 
     enough for the primitive, but this is not a secure form of padding and 
     is no longer used. A modern padding scheme aims to ensure that the 
     attacker cannot manipulate the plaintext to exploit the mathematical 
     structure of the primitive..."

If you want to implement your own RSA encryption, then look at PKCS#1 
(currently at version 2.1):


>> There are a ton of attacks on direct RSA encryption.
>I'm blissfully unaware, I'll do some digging around, but any recommendations 
>are welcome.

Dan Boneh's article, "Twenty Years of Attacks on the RSA Cryptosystem", is 
a good start:


>I'm basically trying to handle 2 encryption related problems:
>#1 backing up files that are distributed to untrusted (as much as possible)
>    peers.  Only the one encrypting should ever be able to decrypt the files.
>    I was planning on using RSA with a user selected key size.  Possibilities
>    for implementations include Crypto.PublicKey.RSA, a wrapper around GPG,
>    and a wrapper/bindings for openssl.

If "only the one encrypting should ever be able to decrypt the files", then 
why not use symmetric encryption?  It's much faster, and probably stronger 
in the long run (since most people don't use 8192-bit RSA keys).

If you must use public-key crypto, use GPG.  Avoid X.509:


Also, avoid PKCS#12:


Don't forget to apply an authentication scheme to the data if there's any 
possibility that the data might be manipulated.

>#2 Securely communications between peers (of encrypted files).  Possibly
>    with out of band communication of public keys (I.e. manual peer
>    introduction by the admin).

This is too vague for me to recommend anything, but it sounds like GPG 
might work here.

And don't forget about random number generation.  All your crypto relies 
upon it, but people screw up the implementations all the time.  Don't be 
one of those people!

Good luck,
  - Dwayne

Dwayne C. Litzenberger <dlitz at dlitz.net>
  Key-signing key   - 19E1 1FE8 B3CF F273 ED17  4A24 928C EC13 39C2 5CF7
  Annual key (2008) - 4B2A FD82 FC7D 9E38 38D9  179F 1C11 B877 E780 4B45
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: Digital signature
Url : http://lists.dlitz.net/pipermail/pycrypto/attachments/20080909/27dc45da/attachment.pgp 

More information about the pycrypto mailing list