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**

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**