0

Public key: $(e,n) = (17, 1 066 601)$

Private key: $d = 939 293$

Message: 452423293428

Table:

enter image description here

Digital signature:

I want to decrypt and encrypt the message by:

$P = C^d (mod 1 066 601)$

$C = P^e (mod 1 066 601)$

My book says, I have to group the resulting numbers into blocks of 2m decimal digits, where 2m is the largest positive even integer such that all blocks of number equivalents corresponding to m letters (viewed as a single integer with 2m decimal digits) are less than n, e.g. if $6565<n<656565$ then $m = 2$

So:

$C \equiv 452423^{939293} \equiv 593991 (mod 1 066 601)$

$C \equiv 293428^{939293} \equiv 85260 (mod 1 066 601)$

I also tried blocks of 5 and 7 and 5 works!

enter image description here

Why do you have to group the resulting number into blocks of 2m decimal digits, where 2m is the largest positive even integer?

WinstonCherf
  • 1,022

1 Answers1

1

You do not have to do so, but it is a simple method that works.

You can partition your message as you like, the only requirements are that the largest partition is less that $n$ and, of course, you have an algorithm/protocol which can construct and reconstruct the partitions.

In your example you could encrypt/decrypt each character separately, but this would be inefficient and less secure.

Edit: Your partitions have to be less than the modulus $n$, because if you decrypt an encrypted message with $m^d \pmod n$ then the result is less that $n$. And you loose security with small partitions because you might take the $e^{th}$ root for smaller $e,$ e.g. if $e=3$ and if you encrypt 'x' you have $33^3 = 35937$ and you can decrypt without knowing $d$, simply by computing $35937^{1/3}= 33.$

gammatester
  • 18,827
  • Thnx for your answer! So in this example you can take blocks of 1, 2, 3, 4, 5 or 6 decimal digits but it goes wrong when you take blocks of 7. Why is the requirements that the largest partition is less than n? – WinstonCherf Dec 10 '17 at 15:50