Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
I commented the code. Should be easier to understand now. –  Saduff Apr 1 '12 at 14:14
add comment

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
    
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
1  
@PaŭloEbermann, I think the other answer was partially correct. So, I've combined them. –  mikeazo Apr 3 '12 at 17:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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