CryptoChallenges/42.py at master · Maegereg/CryptoChallenges · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import convert
import decimal as dec
import hash
import math
import rsa

class SignatureChecker:
	def __init__(self):
		self.pubKey, self.privkey = rsa.keygen()

	def checkSignature(self, signature, message):
		return rsa.checkSignature(message, signature, self.pubKey)

	def getPubKey(self):
		return self.pubKey

'''
Based on the nth root algorithm derived from Newton's method
(https://en.wikipedia.org/wiki/Nth_root_algorithm)
Returns the integer root (the largest integer x for with x**n <= k)
'''
def nthRoot(k, n):
	x = k
	y = (x+1) // 2
	while y < x:
		x = y
		y = ((n-1)*x + k // pow(x, n-1)) // n
	return x

'''
First, the cube root approach
'''
def forgeSignature(message, pubKey, hashFunction=hash.sha256):
	if pubKey[0] != 3:
		raise Exception("Cannot forge a signature for e != 3")

	blockLen = rsa.getBlocklen(pubKey)

	digest = convert.intToByteString(hashFunction(message))

	passableSignature = chr(0)+chr(1)+chr(0xff)+chr(0)+digest

	passableSignature = passableSignature.ljust(blockLen, chr(0))

	integerValue = convert.byteStringToInt(passableSignature)
	root = nthRoot(integerValue, 3)
	if root**3 == integerValue:
		toReturn = root
	else:
		toReturn = root+1
	return rsa.decodeCiphertext([toReturn], pubKey)


'''
Approach based on Bleichenbacher's math
Currently broken
'''
def alternateForgeSignature(message, pubKey, hashFunction=hash.sha256):
	if pubKey[0] != 3:
		raise Exception("Cannot forge a signature for e != 3")

	blockLen = rsa.getBlocklen(pubKey)
	digestInt = hashFunction(message)

	hashLen = len(chr(0)+convert.intToByteString(digestInt))*8
	bitLen = blockLen*8

	dec.getcontext().prec = bitLen

	N = pow(2, hashLen) - digestInt

	cubeRoot = dec.Decimal(2)** (dec.Decimal(bitLen-15)/dec.Decimal(3.0)) - dec.Decimal(N) * dec.Decimal(2)**(dec.Decimal(bitLen-24-hashLen) - dec.Decimal((bitLen-15)*2)/dec.Decimal(3))

	print repr(convert.intToByteString(digestInt))
	print repr(convert.intToByteString(pow(int(cubeRoot), 3)))

	return rsa.decodeCiphertext([cubeRoot], pubKey)


if __name__ == "__main__":
	message = "hi mom"
	pubKey, _ = rsa.keygen()
	fakeSignature = forgeSignature(message, pubKey)
	print rsa.flawedCheckSignature(message, fakeSignature, pubKey)