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:


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);
  N2, M, R1, R2, R3, Sign1, Sign2 : TFGInt;
  str : String;

  procedure L(N : TFGInt; var u : TFGInt);
    one : TFGInt;
    Base10StringToFGInt('1', one); // one = 1
    FGIntSub(u, one, u); // u = u - one
    FGIntDiv(u, N, u); // u = u / N
  // 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


And here's the procedure for verifying:

function PaillierVerify(Hm : String; N, G : TFGInt; s1, s2 : String) : Boolean;
  Sign1, Sign2, N2, R1, R2, R3 : TFGInt;
  str : String;
  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
    result := False;



  • $\begingroup$ I commented the code. Should be easier to understand now. $\endgroup$ – 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).

  • $\begingroup$ 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. $\endgroup$ – Paŭlo Ebermann Apr 3 '12 at 16:40
  • 1
    $\begingroup$ @PaŭloEbermann, I think the other answer was partially correct. So, I've combined them. $\endgroup$ – mikeazo Apr 3 '12 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.