I'm studing RSA theory, and I've a question about an exercise of an exam of the past year...

The image below is a question for past year's exam. Is a True/False answer.

A and B for me are clear. A is True, whereas B is False.

But the problem comes with C and D. The bit representative of a 1357 modulus is 10.4 bits. Theoretically I would say that the Input blocksize (m) should be small than n (modulus). So 10 bit chunksize as input should be correct, as 11 bit input is exceeds 10.4 bit and the input cannot be larger than the modulus (two different values will give the same encrypted result)

But the problem is the output. As the modulus is 10.4 the output is required to be 11 bit... because c= m^e mod n being m=10bit but n=10.4 bit will result in (at least) C=10.4 bit (should be coded as 11 bit)

So the problem arises at the decryption... makes no sense to decrypt 11 bit, that should be splitted to 10 bit + 1bit+padding... and this, for me doesn't give the original result.

As I've always understood that Input and Output sizes MUST be equal.

On the exam I would anser T F but C and D I would leave them in blank.

Any of you have a different interpretation of this situation?

Thanks in advanced!

enter image description here


Here's how I would interpret these two questions:

(C): if we are restricted to encrypting plaintexts that are bitvectors of a specific length, is 10 bits the largest bitvector Alice can encode (using Bob's public key), without causing any decryption failures when Bob needs to decrypt?

(D): if we are restricted to encoding ciphertexts as bitvectors of a specific length, is 11 bits the smallest bitvector Alice can produce (using Bob's public key), without causing any decryption failures when Bob needs to decrypt?

  • $\begingroup$ So, C should be True, but D, for me is still False, as then this 11 bits bitvector cannot be decrypted, because is larger than the modulus, isn't it? $\endgroup$ Jan 9 '17 at 20:03
  • $\begingroup$ @ChrisCharlton: 11 bit vectors can represent values larger than the modulus; however it can represent all values smaller than the moduls; and so it could be decrypted (with a possible failure if the value is larger; but that would happen only if the ciphertext wasn't generated by the encryption procedure) $\endgroup$
    – poncho
    Jan 9 '17 at 20:13
  • $\begingroup$ Makes sense, if 11 bits are the output of a 10.4 bit function... will never contain values higher than 10.4 bits. Thank you! $\endgroup$ Jan 9 '17 at 20:24
  • $\begingroup$ @ChrisCharlton: if you really want to thank me, accept and upvote my answer. $\endgroup$
    – poncho
    Jan 9 '17 at 20:29

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.