On the Signature Reblocking Problem in Public Key Cryptosystems

In Chapter 5 of the book I write about my good fortunate meeting two of the RSA algorithm inventors at MIT, and collaborating with them. As soon as I had a chance to ready their (as yet unpublished) paper, the “reblocking problem” bothered me as a rather awkward implementation detail. This refers to a technical issue described in Section X (Avoiding “Reblocking” When Encrypting A Signed Message) of the foundational RSA paper that is described in a nutshell in the first sentence.

A signed message may have to be “reblocked” for encryption since the signature n may be larger than the encryption n (every user has his own n).

The solution I immediately saw was simplicity itself, so simple that I recall going over the details to triple-check it because it was too easy. After summoning the courage to drop in on Dr Rivest in his office, and when I showed it to him he called in Dr Adleman from next door, as I recall they were kicking themselves for not seeing it. All you do is reverse the order of computation to ensure the domains of the decrypting and encrypting functions compose properly (smaller domain first).

It was too late to update their paper which was about to be published, so Dr Rivest suggested I write a letter to appear in the same volume of the journal Communications of the ACM which he happened to help edit.

My modest contribution to the RSA algorithm predates the ACM online digital library, but I was recently able to obtain a scan posted here for the historical record.


  • A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, by Ron L. Rivest, Adi Shamir, and Leonard Adleman

  • On the Signature Reblocking Problem in Public-Key Cryptosystems by Loren Kohnfelder, Communications of the ACM 21 (Feb. 1978), page 179.