encrypt.py

import hashlib
import gmpy2
import os
from secret import x, seed


class DSA():
	def __init__(self):
		self.g = 88125476599184486094790650278890368754888757655708027167453919435240304366395317529470831972495061725782138055221217302201589783769854366885231779596493602609634987052252863192229681106120745605931395095346012008056087730365567429009621913663891364224332141824100071928803984724198563312854816667719924760795
		self.y = 18433140630820275907539488836516835408779542939919052226997023049612786224410259583219376467254099629677919271852380455772458762645735404211432242965871926570632297310903219184400775850110990886397212284518923292433738871549404880989194321082225561448101852260505727288411231941413212099434438610673556403084
		self.p = 89884656743115795425395461605176038709311877189759878663122975144592708970495081723016152663257074178905267744494172937616748015651504839967430700901664125135185879852143653824715409554960402343311756382635207838848036159350785779959423221882215217326708017212309285537596191495074550701770862125817284985959
		self.q = 1118817215266473099401489299835945027713635248219
		self.x = x

	def sign(self, m, k):
		h = int(hashlib.md5(m).hexdigest(), 16)
		r = pow(self.g, k, self.p) % self.q
		s = int(((self.x * r + h) * gmpy2.invert(k, self.q)) % self.q)
		return (r, s)

	def verify(self, m, r, s):
		if 0 < r and r < self.q and 0 < s and s < self.q:
			h = int(hashlib.md5(m).hexdigest(), 16)
			w = gmpy2.invert(s, self.q)
			u1 = (h * w) % self.q
			u2 = (r * w) % self.q
			v = ((pow(self.g, u1, self.p) * pow(self.y, u2, self.p)) % self.p) % self.q
			return v == r
		return None


class LCG():
	def __init__(self):
		self.a = 3437776292996777467976657547577967657547
		self.b = 828669865469592426262363475477574643634
		self.m = 1118817215266473099401489299835945027713635248219
		self.seed = seed
		self.state = (self.a * self.seed + self.b) % self.m

	def next_number(self):
		self.state = (self.a * self.state + self.b) % self.m
		return self.state


generator = LCG()
signature = DSA()

for _ in range(2):
	message = "VolgaCTF{" + os.urandom(16).encode('hex') + "}"
	k = generator.next_number()
	(r, s) = signature.sign(message, k)
	print (message, r, s)
	print signature.verify(message, r, s)