So I’m writing an essay about the Paillier cryptosystem, and have been having some troubles figuring it out. I’ve tried asking questions about it on 4 cryptography/math specific forums, but no one has been able (or just not been bothered…) to help. There are some pretty smart guys on here so I figured there might be a chance that there’d be someone on here that could help me. I’ll do a worked example and point out where I’m having problems:

Key Generation

n=pq

p= 53, q=61

n = 3233 = 53*61

(lambda) = lcm (p-1,q-1)

(lambda) = lcm(52,60) = 780

g = y^n mod n^2

g = 20^3233 mod 3233^2 = 9283294

This is the first step that I’m a bit confused about. From what I understand you choose a random y ingeger and calculate g from that, correct?

Encryption

Message= 13

r = 17

ciphertext = g^m * r^n mod n^2

Ciphertext = 9283294^13 * 17^3233 mod 3233^2 = 4267322

Decryption

m = ((L(c^(lambda) mod n^2)/(L(g^(lambda) mod n^2)) mod n

where L = (u-1)/n

I’m not completely sure what u is, but from what I gather it’s a “dummy variable” meaning that you use whatever is in front of it as the variable (without the modulo)

m = (((c^lambda -1)/n)(c^lambda mod n^2)/((g^lambda -1)/n)(g^lambda mod n^2)) mod n

m= (((4267322^780 - 1)/3233)(4267322^780 mod 3233^2)/((9283294^780 - 1)/3233)(9283294^780 mod 3233^2))mod 3233

When I enter this into maple, I get the following message “Error, the modular inverse does not exist”. I’ve managed to not get an error message before, but message received has not been the same as was sent. Can anyone point out where I’m going wrong here?

Thanks