inverse random integer k

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

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/c.../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:

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