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 ?
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$.