rivest-shamir-adleman-250 writeup (Zeromutarts.de 2013) 

## using SAGE RSA
n = 80646413
p = floor(sqrt(80646413))

### Finding Factor p*q = n
while(true):
    if (n%p == 0):
        print p
        break
    p=p+1

q = n / p
print q

#### phi(n)
n1 = (p-1) * (q-1)
print n1

e =5
d = e^-1 % n1
print d  ### got private key

###Fast Exponentiation Algorithms
def expo(c,d,n):
    if (d==1):
        return c%n
    if (d==2):       
        return c*c % n
    if (d%2==0):
        return expo(expo(c,d/2,n),2,n)
    else:        
        return c*expo(expo(c,(d-1)/2,n),2,n)

        
cipher = [72895864,15633602,38820479,60303684,7458706,60299530,20682371,54642689,26066811,32615038,35349196,76400140,38820479,56463813,80491201,76400140,35349196,69567074,26066811,76400140,74270178,76127647,76127647,15633602,76400140,60303684,38820479,56463813,60303684,76400140,72844764,76127647,69302434,15633602,80491201,76400140,6809712,26066811,76400140,42498798,60299530,76127647,69302434,80491201,33234011]

flag = ''
for c in cipher:
    flag = flag+ chr(expo(c,d,n)%n)
print flag
flag{rivest_and_the_cool_gang_would_be_proud} 

 useful links to study:

http://www.programminglogic.com/fast-exponentiation-algorithms/

http://stackoverflow.com/questions/4078902/cracking-short-rsa-keys

Comments

Post a Comment

Popular posts from this blog

Baby Step Giant Step Algorithm Python Code

#Baby Step Giant Step DLP problem y = a**x mod n #Example 70 = 2**x mod 131 y = 70 a = 2 n = 131 s = floor(sqrt(n)) A = [] B = [] for r in range(0,s): value = y*(a^r) % n A.append(value) for t in range(1,s+1): value = a^(t*s) % n B.append(value) print A print B x1,x2 =0,0 for r in A: for t in B: if r == t: x1 = A.index(r) x2 = B.index(t) print x1,x2 break print 'the value of x is ', ((x2+1)*s - x1) % n # Answer
Read more

Berlekamp–Massey algorithm

The Berlekamp–Massey algorithm is an algorithm that will find the shortest linear feedback shift register for a given binary output sequence. The algorithm will also find the minimal polynomial of a linearly recurrent sequence in an arbitrary field. I have used sage for computing this program. # Berlekamp-Massey Algorithm #from __future__ import print_function s = [GF(2)(0), 0, 1, 0, 0, 0, 0, 0, 1, 1, 0] #input sequence n = len(s) C = [GF(2)(1)] B = [GF(2)(1)] temp = [] T = [] L = 0 N = 0 m = -1 print '----- n',n print '-----------------------------------------------------------------------' while N < n: temp = B d = s[N] for i in range(1,L+1): d = d + C[i]*s[N-i] print '----- d ',d if d == 1: T = C temp = [ 0 for i in range(int(N-m))] + temp if len(C) < len(temp): C = C + [0 for i in range(len(temp)-len(C))] else: temp = temp +...
Read more

Python Speech recognition for Mac OS X

Hi Folks, I have been been searching for the    Python Speech recognition package especially for Mac OS.  I am not happy with the search results. Finally I got  https://pypi.python.org/pypi/SpeechRecognition/ (SpeechRecognition works only for the Linux distributions and Windows.) But I made it working for the Mac OS X by using flac.  Following are the instructions to make it run and modified code,  Prerequisite: Install Xcode in Unix Development mode Install Xcode - Command Line tools (Type ' xcode-select —install' in the terminal ) Install Port or Brew ( port    [or]   Brew   ) sudo brew install portaudio  [or]  sudo port install portaudio (for loading mic drivers) sudo pip install pyaudio [or] sudo easy_install install pyaudio (Mic Sources) sudo pip install SpeechRecognition [or] sudo easy_install install SpeechRecognition sudo port install flac Once you have finished w...
Read more