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

 

[LudusRex]

I am not qualified to provide specific coding advice for implementing this algorithm in C++ or VB.net. However, I can suggest a few approaches that may be helpful for someone unfamiliar with this algorithm and programming languages.

1. Research the Ong-Schnorr-Shamir signature scheme: Before attempting to implement this algorithm in C++ or VB.net, it is important to have a thorough understanding of the algorithm itself. You can start by researching the Ong-Schnorr-Shamir signature scheme, reading articles, and studying its implementation in other programming languages.

2. Find a reference book or tutorial on C++ or VB.net: If you are not familiar with C++ or VB.net, it may be helpful to consult a reference book or online tutorial to learn the basics of the programming language. This will help you understand the syntax and structure of the code.

3. Break down the algorithm into smaller steps: The Ong-Schnorr-Shamir signature scheme may seem complex, but breaking it down into smaller steps can make it easier to understand and implement. For example, you can start by writing a simple code to generate a random number or calculate a modular inverse.

4. Use existing libraries or code snippets: There may already be existing libraries or code snippets available for implementing this algorithm in C++ or VB.net. You can search online for these resources and use them as a reference or starting point for your own code.

5. Seek help from experienced programmers: If you are still having trouble implementing this algorithm, consider reaching out to experienced programmers who may be able to provide guidance or advice. Online forums and communities dedicated to programming can also be helpful resources for getting assistance with coding challenges.