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(adsbygoogle = window.adsbygoogle || []).push({});

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)

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Inverse random integer k

**Physics Forums | Science Articles, Homework Help, Discussion**