C/C++ How can I implement this in C++ or VB.net?

[bhardjono]

Please help - I am helping a student who is trying to translate Ong-Schnorr to C++ or VB.net language. My major was electronics so I am not sure how to interpret inverse random integer k. Any one ? or suggest me a reference to read on - much thanks, newbie

Ong-Schnorr-Shamir (from Briuce's Applied Cryptography p.418 chp 20.5)
This signature scheme uses polynomials modulo n [1219,1220]. Choose a large integer n (you need not know the factorization of n). Then choose a random integer, k, such that k and n are relatively prime. Calculate h such that
h = –k^-2 mod n = -(k^-1)^2 mod n
The public key is h and n; k is the private key.
To sign a message, M, first generate a random number, r, such that r and n are relatively prime. Then calculate:

S1 = 1/2 * (M/r + r) mod n
S2 = k/2 * (M/r – r) mod n
The pair, S1 and S2, is the signature.
To verify a signature, confirm that
S1^2 + h * S2^2 identical to M (mod n)

 

[bhardjono]

Please help - I am helping a student who is trying to translate Ong-Schnorr to C++ or VB.net language. My major was electronics so I am not sure how to interpret inverse random integer k. Any one ? or suggest me a reference to read on - much thanks, newbie

Ong-Schnorr-Shamir (from Briuce's Applied Cryptography p.418 chp 20.5)
This signature scheme uses polynomials modulo n [1219,1220]. Choose a large integer n (you need not know the factorization of n). Then choose a random integer, k, such that k and n are relatively prime. Calculate h such that
h = –k^-2 mod n = -(k^-1)^2 mod n
The public key is h and n; k is the private key.
To sign a message, M, first generate a random number, r, such that r and n are relatively prime. Then calculate:

S1 = 1/2 * (M/r + r) mod n
S2 = k/2 * (M/r – r) mod n
The pair, S1 and S2, is the signature.
To verify a signature, confirm that
S1^2 + h * S2^2 identical to M (mod n)

3 mod 10 = 3
4 mod 10 = 4
10 mod 3 = 1
10 mod 4 = 2

in Schnorr
h= -k^(-2) mod n
h= -(k^(-1))^2 mod n
Hence for 2 primes
9 mod 2 = 1
(3)^2 mod 2 = 1
Therefore k^(-1) = 3 Is this right please your opinion please - thanks in advance

 

[schip666!]

I'm not entirely clear what your question is, but if it's how to get a (sorta) random number in C... The stdlib has: int rand ( void ); which you can seed with srand(). A man page is here:
http://www.cplusplus.com/reference/clibrary/cstdlib/rand/

 

[rcgldr]

I don't know about encryption, but know a bit about finite field math and don't understand your examples. Using 5 as n, you get these tables for finite field math modulo 5:

add                   subtract (left - top)

   0  1  2  3  4         0  1  2  3  4
  --------------        --------------
0| 0  1  2  3  4      0| 0  4  3  2  1
1| 1  2  3  4  0      1| 1  0  4  3  2
2| 2  3  4  0  1      2| 2  1  0  4  3
3| 3  4  0  1  2      3| 3  2  2  0  4
4| 4  0  1  2  3      4| 4  3  2  1  0

multiply              divide (left / top)

   0  1  2  3  4         0  1  2  3  4
  --------------        --------------
0| 0  0  0  0  0      0| x  0  0  0  0
1| 0  1  2  3  4      1| x  1  3  2  4
2| 0  2  4  1  3      2| x  2  1  4  3
3| 0  3  1  4  2      3| x  3  4  1  2
4| 0  4  3  2  1      4| x  4  2  3  1

All non-zero numbers can be considered to be a power of 2. Multiply and divide can be peformed by taking the logs of finite field numbers and adding or subracting modulo 4 (n-1), the exponentiating the result. This doesn't work for all finite fields, in this case, 2 is a "primitive" for a finite field modulo 5.

2⁰ = 1
2¹ = 2
2² = 4
2³ = 3

In the general case of a finite field number to determine (-1/k)² , you first find i = ( (0 - k) mod n). Then you need to do a table lookup, or implement an algorithm to solve for j where ((i x j) mod n) = 1, then 1/i = j. (1/i)² would be ((j²) mod n).