2

I am writing an article about a late-1980s system that uses the RSA algorithm for the purpose of authentication. However, rather than the usual approach of encrypting a hash of the message using a private key, in this case the entire message is encrypted, using:

Modulus:          n = 0x35... # length 51 bytes / 406 bits
Public exponent:  e = 3       # to maximize performance
Private exponent: d = ...     # such that d⋅e ≡ 1 (mod φ(n))

The message (typically 250 bytes in length) is split into multiple blocks of 50 bytes each. Each block is then encrypted independently by first adding a prefix (where : represents concatenation):

plaintext = 0x15 : block
ciphertext = (plaintext ^ d) mod n

When the ciphertext is read, each block is recovered by decrypting:

plaintext = (ciphertext ^ 3) mod n
assert plaintext[0] == 0x15
block = plaintext[1..]

In terms of authentication, verifying that the first byte of the plaintext is 0x15 is not particularly useful - decrypting random ciphertext would pass that check approximately 2% of the time.

Instead, this system relies on the fact that, if the message was not encrypted using the correct private key, after decryption the message itself would be invalid.

Is there a name for this (unconventional?) use of public-key cryptography for authentication? Could it be considered a form of digital signature?

When describing this system, is it correct to refer to the use of the private exponent as "encrypting" and the public exponent as "decrypting", as above? Could the ciphertext be described as "encrypted", "signed" or neither of these?

3

The use of the private key cannot reasonably be called “encrypting” since the security objective is to ensure authentication, not confidentiality. There can't be any encryption going on since all the information to reverse it is public. What you describe is a signature scheme, specifically a signature scheme with recovery since the same encoded message contains both the information needed to verify the authenticity and the information needed to reconstruct the message. The main difference with modern signature schemes (PKCS#1 v1.5, PSS) is that this scheme is broken in several ways.

Modern RSA signature schemes prevent the formation of forged signatures by including a fixed “padding string” at some part of the decoding. Both PKCS#1 methods mandate at least 8 bytes of padding. The scheme you describe doesn't have anything like this (except the leading byte, but as you note it has negligible impact) and so has to rely on plaintext validity.

The leading 0x15 at least prevents the ability to forge valid messages with lots of leading null bytes. The public exponentiation operation is easily reversible if it doesn't wrap around: if M is less than the eth root of n then taking the eth root of M (as an integer) would result in a valid signature. Mandating a high bit set causes all such M to be invalid. The leading 0x15 also makes it difficult to generate valid signatures by multiplying valid signed messages together (but only if you don't hit that ~2% chance of randomly getting the leading 0x15 in the result).

Splitting the message enables the trivial attack of reordering the blocks of a signed message. Modern signature schemes use a hash to condense the message to a length that the asymmetric operation supports, ensuring that a given signature is only valid for the one message that has the signed hash.

  • Very useful, thank you. So, in my article, should I refer to the operation ciphertext = (plaintext ^ d) mod n as "signing", and to the resulting ciphertext as "signed" rather than "encrypted"? What term should be used for plaintext = (ciphertext ^ 3) mod n? Is "verification" the right term for this operation to recover the plaintext? – RetroSpark Sep 18 at 9:46
  • @RetroSpark Strictly speaking, the signature mechanism is the whole process including splitting the message and adding 0x15. The opposite operation is a “verification with recovery” (that's a somewhat standard term, for example PKCS#11 uses it, even though it isn't very common). The technical name for the exponentiation itself is that it's a pair of trapdoor functions (^d in the hard direction, ^e in the easy direction). – Gilles 'SO- stop being evil' Sep 18 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.