# Implementing Paillier Signature Scheme in Delphi

I've been trying to implement the Paillier Signature Scheme in Delphi, but I can't get it to work and I don't know where the problem is. First of all, I got my info about the scheme from this paper. The signature scheme is on page 9.

The problem is that the signature is never valid according to this code. It's either the Sign or Verify procedure is incorrect, or both.

I used the following parameters for testing (in base-10/decimal):

P = 321338679795746323343853926877767586281
Q = 213863969755443035524230640901647169597
N = 68722765697091485723721317211100788462880275370593368117496797396254137498757
G = 7088302623238842934503017061266983249110295497723677422985727247787796184548356392037437054001558709620406810910526838807521727206527643
Lambda = 17180691424272871430930329302775197115586268180260544689657178207118680685720


The parameters should be correct, because PaillierEncrypt and PaillierDecrypt work fine. I try to sign the message "Saduff" and I use Whirlpool-512 for the hash, so

h(m) = 99241F4CD544CB9BCC5C15992BF61CC74478C250606A82F8BEAEBB4585EB19471E943905F14B0F75B0E24BDDDAFD7D18525BD617F9D811B75EFD93101B2A7A81


With the function I coded, I got these results with the above parameters (in base-10/decimal):

s1 = 67636217684497729547386957113582981960538961939974838591970596747061292253861
s2 = 61648177206819105012398859677197570343483892663060846824771826997744146867920


However, on verify, I got this:

0D59BA9B52FBE2D72E21E905099F6156DD82FD72FD636575447C59717D789BCE73A4FA59C9E0206812339DA2E2EF7B821136524E9521BEE7CC7C7BCA2978712C


And since that is not equal to h(m), the signature gets rejected.

Here's the procedure for signing:

procedure PaillierSign(Hm : String; N, G, Lambda : TFGInt; var s1, s2 : String);
var
N2, M, R1, R2, R3, Sign1, Sign2 : TFGInt;
str : String;

procedure L(N : TFGInt; var u : TFGInt);
var
one : TFGInt;
begin
Base10StringToFGInt('1', one); // one = 1
FGIntSub(u, one, u); // u = u - one
FGIntDiv(u, N, u); // u = u / N
FGIntDestroy(one);
end;
begin
// Calculate s1

FGIntSquare(N, N2); // N2 = N^2
ConvertHexStringToBase256String(Hm, str); // Hm -> str
Base256StringToFGInt(str, M); // str -> M
FGIntMontgomeryModExp(M, Lambda, N2, R1); // R1 = M^Lambda mod N2
L(N, R1);
FGIntMontgomeryModExp(G, Lambda, N2, R2); // R2 = G^Lambda mod N2
L(N, R2);
FGIntModInv(R2, N, R3); // R3 = R2^-1 mod N
FGIntMulMod(R1, R3, N, Sign1); // Sign1 = R1 * R3 mod N
FGIntToBase256String(Sign1, s1); // Sign1 -> s1
ConvertBase256StringToHexString(s1, s1); // convert s1 to hexadecimal

// Calculate s2

FGIntChangeSign(Sign1); // Sign1 = -Sign1
FGIntAdd(Sign1, N, R1); // R1 = Sign1 + N
FGIntMontgomeryModExp(G, R1, N, R2); // R2 = G^R1 mod N
FGIntMulMod(M, R2, N, R1); // R1 = M * R2 mod N
FGIntModInv(N, Lambda, R2); // R2 = N^-1 mod Lambda
FGIntMontgomeryModExp(R1, R2, N, Sign2); // Sign2 = R1^R2 mod N
FGIntToBase256String(Sign2, s2); // Sign2 -> s2
ConvertBase256StringToHexString(s2, s2); // convert s2 to hexadecimal

FGIntDestroy(N2);
FGIntDestroy(M);
FGIntDestroy(R1);
FGIntDestroy(R2);
FGIntDestroy(R3);
FGIntDestroy(Sign1);
FGIntDestroy(Sign2);
end;


And here's the procedure for verifying:

function PaillierVerify(Hm : String; N, G : TFGInt; s1, s2 : String) : Boolean;
var
Sign1, Sign2, N2, R1, R2, R3 : TFGInt;
str : String;
begin
result := False;
ConvertHexStringToBase256String(s1, str); // s1 -> str
Base256StringToFGInt(str, Sign1); // str -> Sign1
ConvertHexStringToBase256String(s2, str); // s2 -> str
Base256StringToFGInt(str, Sign2); // str -> Sign2
FGIntSquare(N, N2); // N2 = N^2

FGIntMontgomeryModExp(G, Sign1, N2, R1); // R1 = G^Sign1 mod N2
FGIntMontgomeryModExp(Sign2, N, N2, R2); // R2 = Sign2^N mod N2
FGIntMulMod(R1, R2, N2, R3); // R3 = R1 * R2 mod N2
FGIntToBase256String(R3, str); // R2 -> str
ConvertBase256StringToHexString(str, str); // convert str to hexadecimal

If Hm = str Then
result := True
Else
result := False;

FGIntDestroy(Sign1);
FGIntDestroy(Sign2);
FGIntDestroy(N2);
FGIntDestroy(R1);
FGIntDestroy(R2);
FGIntDestroy(R3);
end;


Thanks.

-
I commented the code. Should be easier to understand now. –  Saduff Apr 1 '12 at 14:14

I'm doing this as another answer since my first answer was incorrect.

Your calculation of s2 is incorrect. In python I did it as

s2 = pow(m*pow(inverse(G,N),s1,N), inverse(N,Lambda), N)

Mathematically it would be $((G^{-1})^{s1}\bmod{N})$ for the term $G^{-s1}$ or equivalently $(G^{s1})^{-1}\bmod{N}$. In words, the inverse of $G$ (modulo $N$) raised to the power $s1$ (again modulo $N$).

Also, your $h(m)$ is too large. It is bigger than $N^2$. You'll have to use larger primes for correctness if you are going to be using large messages (larger primes will also be necessary for security).

-
Yes, that's it. It works now. Thanks a lot. :) –  Saduff Apr 2 '12 at 0:01
If you think your other answer is incorrect, you can delete it (there is a delete button for the author). Or edit it to actually make it right. –  Paŭlo Ebermann Apr 3 '12 at 16:40
@PaŭloEbermann, I think the other answer was partially correct. So, I've combined them. –  mikeazo Apr 3 '12 at 17:04