Sage drill 2

nb.sage

import hashlib

####Exercise 1###

#Inputs:
# sciper: the fixed prefix of the hash function
# input: the message to hash
#Returns
# trunc_40(MD5(sciper||input))
def modified_md5(sciper, input):
  return hashlib.md5(str(sciper)+str(input)).hexdigest()[:10]


#Input:
# sciper: your sciper number (prefix of the hash function)
#Output: 
# [x0,M1,M2] where M1 and M2 are the two colliding inputs and x0 the initial value of Floyd's algorithm
def floyd(sciper):
  x0 = "ferhatelmas"
  t, tm = modified_md5(sciper, x0), x0
  h, hm = modified_md5(sciper, t), t
  while t != h:
    t, tm = modified_md5(sciper, t), t
    hm = modified_md5(sciper, h)
    h = modified_md5(sciper, hm)
  
  t = x0
  while t != h:
    t, tm = modified_md5(sciper, t), t
    h, hm = modified_md5(sciper, h), h

  h, hm = modified_md5(sciper, t), t
  while t != h:
    h, hm = modified_md5(sciper, h), h

  return [x0, tm, hm]

def ex1():
  print floyd(214805)

####Exercise 2####

#Input: the message to hash
#Output: A hash of the input
def H(input):
    return int(hashlib.sha1(str(input)).hexdigest()[:11],16)

#Input:
# M: the message to sign
# d: the private key
#Output:
# An ECDSA signature si = (r,s)
def ECDSA_sign(M,d):
  q = 6277101735386680763835789423207666416083908700390324961279
  a = 0xfffffffffffffffffffffffffffffffefffffffffffffffc
  b = 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1
  n = 6277101735386680763835789423176059013767194773182842284081
  Gx = 0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012
  Gy = mod(Gx**3 + Gx*a + b, q).sqrt()
  G = EllipticCurve(Integers(q), [a, b])(Gx, Gy)

  K = Integers(n)
  r = s = 0
  while r == 0 or s == 0:
    k = K.random_element()
    r = mod(mod(int((int(k) * G)[0]), q), n)
    s = mod((H(M) + d*r) / int(k), n)
  return (r, s) 

#Inputs:
# M: the signed message
# si:the signature of M
# Q: the public key 
#Output:
# Whether the signature is verified or not
def ECDSA_verif(M,si,Q):
  q = 6277101735386680763835789423207666416083908700390324961279
  a = 0xfffffffffffffffffffffffffffffffefffffffffffffffc
  b = 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1
  n = 6277101735386680763835789423176059013767194773182842284081
  Gx = 0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012
  Gy = mod(Gx**3 + Gx*a + b, q).sqrt()
  G = EllipticCurve(Integers(q), [a, b])(Gx, Gy)

  if min(si) < 0 or max(si) >= n:
    return False
  u1, u2 = mod(H(M)/si[1], n), mod(si[0]/si[1], n)
  x = mod((int(u1)*G + int(u2)*Q)[0], q)
  return int(si[0]) == int(x)

def ex2():
  sciper = 21480500000000000000
  t, tm = sciper + H(sciper), sciper
  h, hm = sciper + H(t), t
  while t != h:
    t, tm = sciper + H(t), t
    hm = sciper + H(h)
    h = sciper + H(hm)
  
  t = sciper
  while t != h:
    t, tm = sciper + H(t), t
    h, hm = sciper + H(h), h

  h, hm = sciper + H(t), t
  while t != h:
    h, hm = sciper + H(h), h

  q = 6277101735386680763835789423207666416083908700390324961279
  a = 0xfffffffffffffffffffffffffffffffefffffffffffffffc
  b = 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1
  n = 6277101735386680763835789423176059013767194773182842284081
  Qx = 0x62b12d60690cdcf330babab6e69763b471f994dd702d16a5
  Qy = mod(Qx**3 + Qx*a + b, q).sqrt()
  Q = EllipticCurve(Integers(q), [a, b])(Qx, Qy)
  d = 651056770906015076056810763456358567190100156695615665659

  si = ECDSA_sign(tm, d)
  if ECDSA_verif(hm, si, Q):
    return (si, str(tm)[6:], str(hm)[6:])
  else:
    print "Couldn't find two messages with identical signatures"
    return None

#####Exercise 3########

#Output: 
# [sqrt1,sqrt2,...,sqrtm] a list of square roots of the x you received. 
def sqrt_ex3():
  x = 4260010601069938309188158856112098890870645650671495050648139321708998508499510781232978609943207404647882606017657077718890818150028292004571258165041869174838544748355225258034188479317543772307284499941751656026878567131602855989763886356084410333067034193745080695725880122720147329540051534983756206891943226591500201407182346309784415604260131509793668029410931613826479306240322198968331910159289035792242648217147106307267641567870517940658229
  p = 2530975194279694358620111138981827172891323587804584709371239885373927037362007457597436503208922415544007327570450479788083583979017079224678590419093
  q = 1222559572160716023935580737201908385976260546156928925862957826488360414279699461383552531120011313067336569178310040662588564585154077376937217164489
  r = 1823055798736488166724237913825351501106743462679726802003357602126377233883557045529391405957446282573382783320799923562002001228776589647919329336709
  n = 5641023130309709227344155390927305648310854075962536442735472202297241550525253841055676406577517957466561157631912667285265863961921509630218648647888539566607138457753337009402588175111468400810545303145059561724690510507557969856317003144602822223723623780368846980073665745468758151567138784689432172067074549067700539593635592732208627026688697808542027981877855750921190104955997812564908856206462635165162260004070526265797590046475338937902193 

  pqr = map(lambda t: mod(x, t).sqrt(all=True), [p, q, r])
  pq = [crt(int(i), int(j), p, q) for i in pqr[0] for j in pqr[1]]
  return [crt(int(i), j, r, p*q) for i in pqr[2] for j in pq]
  
def ex3():
  return sqrt_ex3()

#####Exercise 4########

#Output:
# lambda(n) 
def sqrt_ex4():
  x = 71085628348248695282535420113095220796540127729571805822311887905128722375760200071426250208568046683615613754852445079239701207809895071116156215900647811657396126332716384412868780527194305490188617533893989056003557431042241544801885263973320483680054962316852942872039861384429331147269498982025
  n = 79955891804399389756999142510737600642568572739745309517092662362217568024696537354356541576418967701833062448241680379300766545318538480435660207109140795378003177077917384996138698654078157398800126953959113111394180869729394400401531429206816465977932999258514846253375352881424971187424033224651
  sqrt1 = 51209176743293864076130092569811928775437319779528251756220850280985044955104042975621763853490640408156330098423924775938679270255982488512889080731602263075939696761842266319561318516163531635671011776328581612954296688452555854768072661391362056825123310385621671817532423905671928407806271742607
  sqrt2 = 69356081449618516456111237402140281487221048148907969658522624356272398249538962544893495022952944727782431658534336821315125423141359879437722897373609848868248839944723695273630120725388705851374789476415967984411829051713860210908257148657314038732047784024029182699057536083214311991938982007936

  p = gcd(sqrt2-sqrt1, n)
  return lcm(p-1, n/p-1)

def ex4():
  return sqrt_ex4()

#####Exercise 5##########


def ex5():
  n = 41111955729717247375236262776081707190216413666085776170610499467660828449745807093191521383234882021206245884290681586402556957655251818677502444027074266449808901141593794485319018337400720536098562782839181848463571562932518618784673951505745111032418389247023904745262215399875045901643230201759240358911
  e = 65537
  x = 4083361830662576206787920801850099047880726663883051094176406098772140917889056046656544587319514184314413940189445908242302697124045690834553910528378238664680427078946359900417887364921034980239522790153817951445774696152411410157871231238748924848545511773338654729932243346771921014272999702732564523372

  p, q = 0, 0
  up = next_prime(floor(sqrt(n)))
  down = previous_prime(up)

  while up-down < 10000:
    if up.divides(n):
      p = up
      q = n/up
      break
    if down.divides(n):
      p = down
      q = n/down
      break
    up, down = next_prime(up), previous_prime(down) 
  if p == 0 and q == 0:
    print "Absolute difference between factors is not less than 10000"
    return 

  return power_mod(x, inverse_mod(e, (p-1) * (q-1)), n)