[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: [email protected]*Subject*: Re: Source Code NOT available for ViaCrypt PGP*From*: [email protected] (Norman Hardy)*Date*: Thu, 26 Aug 93 14:39:43 -0700

Regarding Secret key generation. [email protected] (Carl Ellison) says: > The only place to worry is with key generation, > both IDEA and RSA. I presume this is true. I include a Scheme program that finds the first prime in an arithmetic sequence. It uses a function published in Knuth. You can either study my program or compare its output with some program written by someone else to the same spec. If people are interested I will annotate the code and its output better. As it is now the prime that it finds is the last number that it outputs before it stops. Curiously it has a probability of error which is large for small numbers but exceedingly small for large numbers, just the opposite of human testers. I claim that this is a good specification for choosing your secret primes. It has a slight advantage over merely finding the first prime beyond some specified number because that tends to find primes that follow long runs of composites. It just now (as I edited this) found the prime 1000000000000000 00000000000000000000000000000000000000000000000000000000000000913 as the first prime in the sequence 10^80+11*n. I typed (scan (expt 10 80) 11) to the interpreter to get this. It took several minutes. I used MacGambit on a 68030. The output theoretically depends on the hokey random number generator here but if two implementations yield different answers due to different random number generators Knuth and others would be very interested! For use in real RSA application we should include a function that hashes typed in text into a bignum. A good hash of long text is a very good random number! It need not be a crypto hash! (define (ex x)(write x)x) (define (rand31 seed) (lambda()(let* ((hi (quotient seed 127773)) (lo (- seed (* 127773 hi)))(test (- (* 16807 lo) (* 2836 hi)))) (set! seed (if (> test 0) test (+ test 2147483647))) seed))) (define (gbrand max seed)(let* ((rq (rand31 seed)) (nq (let v ((c max)(n 0))(if (< c (expt 2 31)) (cons (let w ((cx c)(nx 1))(if (< cx 2) nx (w (quotient cx 2)(+ nx 1))))n) (v (quotient c (expt 2 31))(+ n 1))))) (z (car nq))(n (cdr nq))(k (+ (* 31 n) z))) (write(list max k z n)) ; max, k, n, z, L and m are non-negative integers. ; 2^(k-1)<=max<2^k. k=31*n+z. 0<z<=31. ; I claim this code is efficient if ; (quotient .. (expt 2 ..)) and (modulo .. (expt 2 ..)) are efficient. (if (= n 0)(lambda () (let r ()(let ((q (modulo (rq) (expt 2 z)))) (if (< q max) q (r))))) (let ((L (quotient max (expt 2 (- k 31)))))(write L) ; max = L*2^(k-31) + m; 0<=m<2^(k-31). L is the high 31 bits of max. (lambda()(+ (* (expt 2 z)(let g ((nx n))(if (= nx 1) (let r ()(let ((q (rq)))(if (< q L) q (r)))) (+ (* (expt 2 31)(g (- nx 1)))(rq)))))(modulo (rq)(expt 2 z)))))))) (load "Random.scm") (define ww (lambda(n x)(display (list n x)) x)) ; The following definition is to ensure that modulo never ; produces negative numbers. (define modulo (let ((modulo modulo))(lambda (a m) (if (negative? a) (- (- m 1) (modulo (-(- m 1) a) m)) (if (positive? a) (modulo a m) 0))))) ; The following is the "Jacobi Symbol". (a|P) (define (j a P) (if (< a 2) (if (= a 1) 1 (if (= a 0) 0 (j (modulo a P) P))) (if (>= a P) (j (modulo a P) P) (if (even? a) (let((q (j (/ a 2) P)) (m (modulo P 8))) (if (or (= m 3)(= m 5))(- q) q)) (let((q (j (modulo P a) a))) (if(or (= (modulo P 4) 1) (= (modulo a 4) 1)) q (- q))))))) (define (mod-exp b p m)(cond ((= p 0) 1) ((even? p)(let ((x (mod-exp b (/ p 2) m)))(modulo (* x x)m))) (#t (modulo (* b (mod-exp b (- p 1) m)) m)))) ; The following is by Solovay & Strassen as presented in Knuth page 396. (define (p-test a P)(if(zero? a)(cdr 2))(and (odd? P) (= (gcd a P) 1) (zero? (modulo (- (j a P)(mod-exp a (/(- P 1) 2) P)) P)))) (quote "The function scan below returns the first prime in the") (quote "arithmetic sequence a + n*b") (define (scan a b)(let* ((g (gcd a b))(n (modulo b 210)) (random (gbrand (+ a (if (positive? b) 0 (* 2000 b))) 228765)) (probe (+ 1 (random)))) (if (> g 1) (list "Always divisible by" g) (let more ((a1 a)(m (modulo a 210))(cn 0)) (if (and (let all ((l (list 2 3 5 7)))(or (null? l) (and (positive? (remainder m (car l))) (all (cdr l))))) (let all ((l 20)(p probe)) (or (zero? l) (and (ww cn (pt p a1)) (all (- l 1)(+ 1 (random))))))) a1 (begin (display ",")(more (+ a1 b)(modulo (+ m n) 210)(+ cn 1)))))))) (define (pc wx) (let zz ((q (- wx 1))(s 0))(if (zero? q) s (zz (- q 1)(+ (if (p-test q wx) 1 0) s))))) ; The following prmality test is from second edition of ; volume 2 of Knuth's "The Art of Computer Programming", ; page 379. (define (pt x n) (or (= n 2) (let* ((pr (let z ((q (- n 1))(k 0))(if (odd? q)(cons q k) (z (quotient q 2)(+ k 1))))) (q (car pr))(k (cdr pr))(nm1 (- n 1))) (let lp ((j 0)(y (mod-exp x q n))) (or (and (= j 0)(= y 1)) (= y nm1) (and (< (+ j 1) k)(lp (+ j 1)(modulo (* y y) n)))))))) ; 10^100-797, 10^200-189, 10^299-171, 10^300-69 are prime. ~. ~.

- Prev by Date:
**Re: Source Code NOT available for ViaCrypt PGP** - Next by Date:
**Re: Commercial PGP: Verifying Trustworthiness** - Prev by thread:
**Re: Source Code NOT available for ViaCrypt PGP** - Next by thread:
**Re: Source Code NOT available for ViaCrypt PGP** - Index(es):