Pure crypto geekery

[Adam Langley <alangley@xxxxxxxxx>]

The DH prime used in Tor is taken from rfc2049, section 6.2 and is
claimed to equal:
2^1024 - 2^960 - 1 + 2^64 * { [2^894 pi] + 129093 }

Of course, one should always check this to make sure that it hasn't
been chosen by the NSA to have nasty properties.

Well, here's a python script to do it. It prints out the calculated
value next to the reference value:

Calculated value on the left, reference on the right

0xFFFFFFFFFFFFFFFFC90FDAA22168C2     0xFFFFFFFFFFFFFFFFC90FDAA22168C2
34C4C6628B80DC1CD129024E088A67CC     34C4C6628B80DC1CD129024E088A67CC
74020BBEA63B139B22514A08798E3404     74020BBEA63B139B22514A08798E3404
DDEF9519B3CD3A431B302B0A6DF25F14     DDEF9519B3CD3A431B302B0A6DF25F14
374FE1356D6D51C245E485B576625E7E     374FE1356D6D51C245E485B576625E7E
C6F44C42E9A637ED6B0BFF5CB6F406B7     C6F44C42E9A637ED6B0BFF5CB6F406B7
EDEE386BFB5A899FA5AE9F24117C4B1F     EDEE386BFB5A899FA5AE9F24117C4B1F
E649286651ECE65381FFFFFFFFFFFFFF     E649286651ECE65381FFFFFFFFFFFFFF
FFL                                  FFL                             


AGL

-- 
Adam Langley                                      agl@xxxxxxxxxxxxxxxxxx
http://www.imperialviolet.org                       (+44) (0)7906 332512
PGP: 9113   256A   CC0F   71A6   4C84   5087   CDA5   52DF   2CB6   3D60

# The `safe prime' from RFC2049 is claimed to equal
# 2^1024 - 2^960 - 1 + 2^64 * { [2^894 pi] + 129093 }

# This script prints out the reference value and the calculated value
# line by line

# Value of pi taken from
# http://www.cecm.sfu.ca/projects/ISC/dataB/isc/C/pi10000.txt

pi_str = '''31415926535897932384626433832795028841971693993751058209749445923078164062862
089986280348253421170679821480865132823066470938446095505822317253594081284811
174502841027019385211055596446229489549303819644288109756659334461284756482337
867831652712019091456485669234603486104543266482133936072602491412737245870066
063155881748815209209628292540917153643678925903600113305305488204665213841469
519415116094330572703657595919530921861173819326117931051185480744623799627495
673518857527248912279381830119491298336733624406566430860213949463952247371907
021798609437027705392171762931767523846748184676694051320005681271452635608277
857713427577896091736371787214684409012249534301465495853710507922796892589235
420199561121290219608640344181598136297747713099605187072113499999983729780499
510597317328160963185950244594553469083026425223082533446850352619311881710100
031378387528865875332083814206171776691473035982534904287554687311595628638823
537875937519577818577805321712268066130019278766111959092164201989380952572010
654858632788659361533818279682303019520353018529689957736225994138912497217752'''.replace('\n', '')

pi = long(pi_str)

a = hex(pow(2, 1024)-pow(2, 960)-1+pow(2, 64) * ( (pow(2, 894) * pi)/pow(10,len(pi_str)-1)  + 129093))

# reference value
b = '''0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E08
8A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B
302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9
A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE6
49286651ECE65381FFFFFFFFFFFFFFFFL'''.replace('\n', '')

print 'Calculated value on the left, reference on the right'
print

i = 0
while True:
	if i*32 > len(a) and i*32 > len(b):
		break
	left = a[i*32:(i+1)*32].ljust(32)
	right = b[i*32:(i+1)*32].ljust(32)
	print left, '   ', right
	i += 1