Implementing Paillier Signature Scheme in Delphi

Question

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.

Answer 1

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).