# Decrypting a message using rem()

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 ?

• Yes it stands for remainder 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$.