Hello i have a problem in decrypting a message using this algorithm

Beforehand : The sender and receiver agree on a large prime p, which may be made public. (This will be the modulus for all our arithmetic.) They also agree on a secret key belongs to {1,2,....,p-1}

Encrypting : The message m can be any integer in the set {1,2,....,p-1}

The encrypted message m* can be computed as follows :

$(m* = rem(mk , p))$

And the decryption will be :

$(m = rem(m*k^-1,p))$

When i try an example ..

$m = 7$ , $k = 13$ , $p = 17$

then $(m* = rem(7 * 13 , 17) = 6)$

So when i try to get m i dont get 7

$(m = rem(6/13 , 17))$

So what's wrong ?

  • $\begingroup$ Yes it stands for remainder $\endgroup$ Jan 25 '16 at 5:37

The issue is that $13^{-1}=4\pmod{17}$, since $13\cdot 4\equiv 1\pmod{17}$. "Division" does not exist here, only multiplication by reciprocals.

Now, we calculate $6\cdot 4\pmod{17}$, and indeed we get $7$, as desired.

By the way, this is not a very good cryptosystem. Suppose we encode each byte of the message this way. Well, most bytes of a text message are spaces. Hence, there will be one encoded number (let's say $6$) sent more than all the others. If the attacker guesses that it corresponds to space (let's say space is encoded as $7$), then all he needs to do is multiply $6$ by the reciprocal of space (in this case $5$, since $7\cdot 5\equiv 1\pmod{17}$) to recover $k=6\cdot 5\pmod{17}=13$.


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.