Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Inverse random integer k

  1. Aug 10, 2010 #1
    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)
     
  2. jcsd
  3. Aug 11, 2010 #2
    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
     
  4. Aug 11, 2010 #3
    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/
     
  5. Aug 11, 2010 #4

    rcgldr

    User Avatar
    Homework Helper

    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:

    Code (Text):

    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.

    20 = 1
    21 = 2
    22 = 4
    23 = 3

    In the general case of a finite field number to determine (-1/k)2 , 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)2 would be ((j2) mod n).
     
    Last edited: Aug 11, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook