T
Tim Churches
Somewhat off-topic (but I _am_ using Python): I am attempting to implement
a hashing function which converts an arbitrary string (or other value) into an
integer which is randomly chosen from a specific domain, F. The domain F is the
set of all quadratic residues modulo p, where p is a safe prime (that is, both p and
q=(p-1)/2 are prime). The results of the hash function need to be random i.e.
the return value, or a sequence of return values, should carry no information
about the original values, and it must be deterministic - same x always results
in the same h(x), and ideally, collision-free, or at least have neglible risk of
collisions.
OK, it is simple to convert a string into a random integer with the appropriate
qualities using SHA-1 hashing - the following does the trick (I think):
import sha
long(sha.new("hello").hexdigest(),16)
With the help of GMP and gmpy, it is also easy to find (or test) a safe prime,
p, and to enumerate the quadratic residues mod p (by using gmpy to evaluate
the Legendre symbol).
However, I am stumped as to how to use the random number produced by SHA-
1 to select a quadratic residue from the domain F. In practice, p needs to be a
very large number (at least 1024 bits), thus enumerating all the quadratic
residues mod p is not feasible. At this point my meagre understanding
of number theory runs out.
Can anyone suggest a method, either mathematical or algorithmic, to make a
random but deterministic (repeatable) selection from domain F?
Tim C
a hashing function which converts an arbitrary string (or other value) into an
integer which is randomly chosen from a specific domain, F. The domain F is the
set of all quadratic residues modulo p, where p is a safe prime (that is, both p and
q=(p-1)/2 are prime). The results of the hash function need to be random i.e.
the return value, or a sequence of return values, should carry no information
about the original values, and it must be deterministic - same x always results
in the same h(x), and ideally, collision-free, or at least have neglible risk of
collisions.
OK, it is simple to convert a string into a random integer with the appropriate
qualities using SHA-1 hashing - the following does the trick (I think):
import sha
long(sha.new("hello").hexdigest(),16)
With the help of GMP and gmpy, it is also easy to find (or test) a safe prime,
p, and to enumerate the quadratic residues mod p (by using gmpy to evaluate
the Legendre symbol).
However, I am stumped as to how to use the random number produced by SHA-
1 to select a quadratic residue from the domain F. In practice, p needs to be a
very large number (at least 1024 bits), thus enumerating all the quadratic
residues mod p is not feasible. At this point my meagre understanding
of number theory runs out.
Can anyone suggest a method, either mathematical or algorithmic, to make a
random but deterministic (repeatable) selection from domain F?
Tim C