import itertools
from sage.all import *

def ASCIIPad(Message):
    K = (map(ord,reversed(Message)));
    #print(K);
    le= len(K);
    #print(le);
    x = [100+K[i] for i in range(le)];
    x = ZZ(x,1000);
    return(x);
def ASCIIDepad(Number):
    n = Number.ndigits() % 3;
    if (n > 0):
        return("This is not a padded ASCII string\n");
    else:
        L = [((Number - (Number % (1000^i)))/1000^i)%1000 - 100 for i in range(Number.ndigits()/3)];
        N = "";
        for i in range(Number.ndigits()/3):
            try:
                N = chr(L[i]) + N;
            except (ValueError):
                return "This is not a padded ASCII string\n";
        return(N);
def rsaencrypt(Message, encrexp, encrmod):
    A = ASCIIPad(Message);
    E = power_mod(A,encrexp,encrmod);
    return(E);
def rsaencryptNoPad(Message, encrexp, encrmod):
    E = power_mod(Message,encrexp,encrmod);
    return(E);
def decrypt(encr,decrexp,encrmod):
    D = power_mod(encr,decrexp,encrmod);
    N = ASCIIDepad(D);
    return(N);
def decryptNoPad(encr,decrexp,encrmod):
    D = power_mod(encr,decrexp,encrmod);
    return(D);
def isqrt(n):
    return int(floor(sqrt(n)))
def usqrt (n):
    ur = isqrt(n)
    if ur ** 2 < n:
        ur = ur + 1
    return(ur)
def FermatAttack (n, rounds):
    st = usqrt(n)
    for x in range(st, st + rounds + 1):
        #print (x-st)
        sq = x ** 2 - n
        y = isqrt(sq)
        if y ** 2 == sq:
            print "Factor found in round {0}".format(x-st+1)
            return(x + y)
    print "Fermat attack failed after {0} rounds".format(rounds)
def RhoAttack(R,rounds):
    a=2
    b=2
    for i in range (1,rounds):
        a=(a^2+1)% R
        c=(b^2+1)% R
        b=(c^2+1)% R
        g=gcd(a-b,R)
        if (1<g and g<R):
                print "Factor found in round {0}".format(i)
                return(g)
    print "The rho attack failed after {0} rounds".format(rounds)
def ISAttack (R):
    R = ZZ(R)
    n = R.ndigits()
    #n = len(R)
    for j in range(1, n + 1):
        x=(R-(R % 10^j))/10^j
        p = gcd(x, R)
        if ((1 < p)and (p<R)):
            return(p)
    print "IS attack unsuccessful"
def ElGamalVerify(Message, y, s, g, b, P):
    v1 = (power_mod(y,s,P) * power_mod(b,y,P)) % P
    v2 = power_mod(g,Message,P)
    if v1==v2 and y<P and s<P:
        return "Signature is Valid"
    else:
        return "Signature is Invalid"

@fork(timeout=2, verbose=True) #if this process takes more than 2 seconds, kill it, the key isnt vulnerable
def HPSonP (Generator, Target, P):
    Unknown = 0
    N = P - 1
    K = factor(N)
    K = list(K)
    #print K
    for pk in K:
        #print pk
        primes =pk[0]
        #Maple code to convert
        #primes = op(1, op(1, op(i, K)))
        #if len(K[i]) == 1:
        #if len(op(i, K)) == 1:
        #    powers = 1
        #else:
        #    powers = op(2, op(i, K))
        powers = pk[1]
        Z = N / primes
        chi = power_mod(int(Generator), int(Z),int(P))
        n = 0
        t = [0]*powers
        a = [0]*powers
        d = [0]*powers
        for j in xrange(0, powers):
            #print j
            if j == 0:
                a[j - 1] = Target
            else:
                Z2 = (d[j - 1 - 1] * power_mod(int(primes),int(j - 1),int(N))) % N
                Pt = power_mod(int(Generator), int(Z2),int(P))# % P
                a[j-1] = (a[j - 1 - 1] / Pt) % P
            y = Z / primes ** j
            t[j-1] = power_mod(int(a[j - 1]),int(y),int(P))# % P
            s = 1
            for k in itertools.count():
                #print "k",k
                if t[j - 1] == s:
                    d[j - 1] = k
                    break
                s = (s * chi) % P
            n = (n + d[j - 1] * primes ** j) % N
        NN = N / primes ** powers
        X = (1 / NN) % primes ** powers
        Unknown = (Unknown + NN * n * X) % N
    #unassign(t)
    return(Unknown)
def Dirichlet (q):
    j=0
    #for j in numpy.arange(0.10e1, infinity + 0.10e1, 0.10e1):
    while True:
        j+=1
        p = 2 * j * q + 1
        if is_prime(p) == True:
            return(p)
def findLargePrimitiveRoot(n,p):
    n=n+1
    eulerp = euler_phi(p)
    Q = list(factor(eulerp))
    while n<p:
        found = True
        for Q2 in Q:
            q=Q2[0]
            totest = power_mod(ZZ(n),ZZ(eulerp/q),ZZ(p))
#            print(totest)
            if totest==1:
                found = False
        if found:
            return n
        n+=1
def BSGB(g,b,p):
    N=p-1
    m=floor(sqrt(N))+1
    B=[]
    G=[]
    B.append(g)
    for j in xrange(1,m):
        B.append(mod(g^j,p))
    #print len(B)
    #print m
    #print B[1]
    p2=B[m-1]
    #print p2
    G.append(p2)
    #print G[1]
    for j in xrange(1,m-1):
        G.append( mod(b*(p2^(-j)),p))
    for i in xrange(1,m-1):
        for j in xrange(1,m-1):
            if B[i]==G[j]:
                L=mod(i+j*m,N)
                return L

###Generate public RSA key
p = next_prime(14232546201475152515401480154369897925870171426987402542155878025872785029856021414417520145202463512)
#p.ndigits()
q = next_prime(80367824806204654062884684650642364261016254620160765460124382604650615046516451640762048418046510650)
#q.ndigits()
n = p*q
#n.ndigits()
e = 65537
print "RSA public key is (",n,",",e,")"

##Generate private key
phiN = euler_phi(p) * euler_phi(q)
d = 1/e % phiN
#d
#gcd(phiN,e) == 1

##Try to attack the key to see if it is safe, if it is, we will be stuck in here forever
#FermatAttack(n,100000)
#RhoAttack(n,2000000)
#ISAttack(n)
#factor(n)

##Encrypted Messages of other students' tests
e = [0] * 41
e[1] = 139926354136492401963226222039335146832973455156364771398686690902579954758039501392025992656342765282232126770816119051391273026838449684509137874054354830258183664358377845723300092574578104263450403
e[2] = 402912099171100964933727529473267682116300028505971835056691637783364720587350427675555442488014650994088251240577427731819447818649730954678452512268106386478700170620218494878493257032598473710300057
e[3] = 932793305670186170577515425631346044715215070656621808400455919648809905742619356717422213654675923217371464161811485526195173810549221372175994160128877819595483560722319412712059724355426365221859711
e[4] = 714136843712721988097958786320470316891266062738664525973724977093212584592902364198430018269637392784967926484991290368217676485039357637585226570124304086332218887122183702451840119438629830673687828
e[5] = 270204398671118820221833589156301352689905306005503881585687460851560523046496220642714468632247953959233228744245024870212090378790733832416932635985488232498795798523182639542668879687617811870066227
e[6] = 1130694481260515439140239058079488161844544063560035878112087155773023933261389885312179902323657123023736720135382768012487185394326922018114710961037001830426169954183569215649026285446014411832591285
e[7] = 2080053352380608117970961848902937987490671993548548858336656200260717119383282091576831488444229422336254538090120131048244478898054047011260505030430908307047466058319917351176285758786076177344196520
e[8] = 926024191771132280144966740216564435035477857231494996391539988595107193104366762306491700047100726787703130536621314148886279962276414941895535750277891000488860918130669134763147472795520318490374915
e[9] = 928691766770140276658443701897209575183947321853324450657831722562361155950475243793492339444003616143454190861530535521892217611545988676720522607926274495277780122365425906600612923420088026147617048
e[10] = 646559892655943889893022952041692977794028548220213310686484503163154457490662602748779811513190984990972622641698869490619388317324888564770540136553199134226691754839524726670293544021163928624452584
e[11] = 2307141613176366375914124490923858271058587880667738513056721293822321746812701884792790184795729787095829327531708347549636890255333260289516179540019332794550854100023061622107967965788996700603706632
e[12] = 671014809852463655202223249741131244179803275621104602114472597958518628646253913986518596051484861715442723701428143573852686040738172923475615368628735240533155375782608471796272546837340146182904784
e[13] = 1497310134003386872049344757274867021843845910471459572109150574868853670673965299080012437109188652535605516850620227394920577388699340324681287262453224330880354793289721191959450933306709487455485293
e[14] = 3269393038323647456266897345105249377009086602973823228697695486831535511736814336962559903018792202324843351147403084555219739789983849920956849637187378976896364184539412694060047290560638625594504536
e[15] = 1851773662826066590717180618656692764762419149872316409343621236296609664084004516481331816256802016776115408062270492793487606454786972853923709875670982793415616995088595802923919120049288497190615006
e[16] = 242849546481972283379929017265065652671802271353781832484533809202698080357801234559646030542882268202664644732559311619531175931619978971210933740151975506120472126676023530414731257407958175869501336487
e[17] = 2814156191689404840166773866552590357773999375707489483534631367499570703378331565034896477841148989631012464726730614162622426740378223740686780874912566710706399669595850622479822367253959001628979438
e[18] = 143913171901402135797716569991502741348337841142944903356499384156460609850328449822320858460073266651425693110795907704344088664722351409836878606370162963674259746351760990218599520242789041482863090
e[19] = 5699123856309103859176327227247925039186750352642929329422588350821146524762039179759236136481558029116348227401991460881531213501542491673838609698504199610371959042500353677426580151115677342180835158
e[20] = 798758084803737191533714189529372077774672017159941383760605050976013805326287000399862899553768363195119202495375005580524431492014354868791292930264321101000281054576389132747662287144085062729604501
e[21] = 1112243060222262087801912385284339647334607756770128757296719589347006659872399632979597105594741322011200251012067856078321001838462647453515785176006515268366793868854654904688688329070338314712489883
e[22] = 5761896066233813040226269453368869859867144318819113008567600209817771596570183565889260216445993638337589351853182839115787476194658648722600431553996499464561846828361826382554953303610044638115183
e[23] = 18292433185967233659277233088521161809395875380664390061658705753539652552562219248378979139527043545035164881928880836849426237501660329423339995514543916109172897263317754720946777804593855979063708
e[24] = 444717053904992635514076227153753011085962137472325316604002244836346034465159542758563358164555985808470008726215118818740378291436170607399247522281265471414370039818256684699403331974555109282736878
e[25] = 22076856321105879485737856700057844020745479003795956589220848008484817378752112484300043163940276569845439664545672882148834093837629290049523453102065258771007941527205014201748865370229041138240296
e[26] = 60600316575106963178598974021373738815159404438389598795071848412001739713255730026876257686042467261630438682570899501256506250226581946201466024170573544073895995519956338766254701182295761005471636
e[27] = 861883160842694104566495264690354461163300509947680261106633525289669981767483428450501168257986330734855421999802335866328597908315720307347115742984839285419816774894074889440739039131035690027251536
e[28] = 442240997582071495777069312972784273642431357470558919343945932964105597927518484908880654566815319533035732176731574540335836357028161016983650165958646241584675910250271380532011549563211780791265654
e[29] = 148393671696594564528753359106429292676418601025615665794500312072871241831764638594699416253873908946696792863482747478313261796242895563210793224128349973557580505214353568992696722442037974846730872
e[30] = 2544268807645406222434007020420564190598159577222682625623387416675565254352937087705763530185032276214635656139613060083687926069162689796629289102835197289137907445647484527929176578767958312229839699
e[31] = 1417806913206090445309202441708485658845501258264878178994336803343337023378146556864313971221037199135624117652704404614710684084238930136621687575906273847682757143145740470019918096877173351288434586
e[32] = 1055808806349297688394669263487417539106304486891949886411594882655476479519238362162586874003277095875119427222060997883868427597512790384052579337599737086381881767414629637070645703520450488431972491
e[33] = 711982154069594552893853063484600092783726418129134311307160025040436149989284568715960191930282782770925204571716533052672784306147534278079799513708431201698608191472729419995699741782770666970916263
e[34] = 437774646717083544703763227200228482748513915549357787747497007844966035420124762594818065743594056863999585037151292743392532629181943006208352420171642858130092278969569562598015865637691679948104718
e[35] = 607014696747085028555362569665587408284735747252264816389578937971219620107994808426809963878060327033526231805760914030743008921807514359662433431072668998360277089527718266893330327469565285308729319
e[36] = 144893234555650257037929002805731897529344129211222463489890386077163022625779340054121064397064400958820959923164038392379795891587450981816016569185008814900923745370732727570914239252451512943191858
e[37] = 435141008854834434993953069169536588173277358363321946548696804583511457438452999470936778170734239395290076220787343947581412554285715081418301113984371220568792697915948985923709394349392227649569195
e[38] = 259340211339616788917276037848982886909171112777892280281391307602469394147322951925760853490976765130881448601358175752488946553731668991500778308365868626707329379354542467169372893810889246840365544
e[39] = 464020655204768554176238487440337772213349865254616582547752783351215928442623081241377584227345740533601310078490211576562341973267339369898346286997209439862861574589757940449694778182853729862665842
e[40] = 332300625603548528605199521614949620114884842494550432019914937067908716396688123053989679030954966915927044650467372019410969921933329318073812443779358742330807244220575185507713129940295726914545762

for i in range(1,41):
    #print "e[", i, "]=", e[i]
    decryptionAttempt = decrypt(e[i],d,n)
    if decryptionAttempt != "This is not a padded ASCII string\n":
        print "\nYour exam number is",i,". The message decrypts to:",decryptionAttempt

##Attack other students private keys
std = [0] * 41
stdN = [0] * 41
stdE = [0] * 41

std[0] = "Amanda Aydelotte"
stdN[0] = 230148249304297492249334888756355770998336502596720221206841628690157648565977514548223711998381463698272773900197925161788784529943743490514702507788699509915084508281144035981045593197355375834591721
stdE[0] = 29
std[1] = "Daniel Shane Newbill"
stdN[1] = 967574639343208278741071316775518135277486659795384950584309985882710579964971148054186110497344699454849834103578911206658394249847380238409818732515668410261754833074899120745362652359525801184485213
stdE[1] = 65537
std[2] = "Harold Martin"
stdN[2] = 2986962367404584290035435101326392304823829203280644555189785294440530883020291360869789087797858506055258550141836900233787271776161806106845176077097620087015602321645111677486222909942535264158359527
stdE[2] = 334534534534554679384793798734534532342343453987298729837493847509348528374983450394758034759835329237456923874659324756928732222272435234523452345243523452345234523452345234534267843
std[3] = "Sidney Smith"
stdN[3] = 11111111111111111111209876543211111111111975308642012345679017283950618024691358086419752977777778310666666637767901239427777777580246913619576543209297160493990641975329791358025495555554327111115501
stdE[3] = 1452791
std[4] = "Shane Odham"
stdN[4] = 1256857500255873079212472368809360296798007226953487587045542748528431965110528024399240124314616587774944173184276807795058598921127060345825206128059532799972506226861639272252391912300874487126608891
stdE[4] = 554849583405234029340398402834345623834534572913492394892734987692347293523423462629
std[5] = "A.J. Bates"
stdN[5] = 1207881304157752430802143696213772020945854257203387951008154876125552842367756902213227521780711503074208562314346081366676186682525054546123860587048489089827347723414457108131458841342572295143333199
stdE[5] = 6553747529
std[6] = "Ethan Stieha"
stdN[6] = 856968042519484984187896188606497449246907048682024628194560772989938248851359909343976968988221614908533309459047226678990393850380769568193387092773846082195760992561225235705742428228638751598109249
stdE[6] = 65537
std[7] = "Paul Siron"
stdN[7] = 5027727154400703485331451728458989364020362337205596677632912575325329902876860150447574233653088653457609577868209011240089909302770594136636704581123022340419914114595661874266250661745991985063918063
stdE[7] =  289189163245342735757604894300490789713286579084767537087904531089079435465790849488940970564687094894354079333
std[8] = "Thomas Jeffs"
stdN[8] = 1309204152650354461377067888571365820318348292368856476220242478903917733861919153374224777740405346103834688822963826030465724055745338194386407559011937132616106471296861300762810767690795965380945109
stdE[8] = 89465123489156321121984651256489123123449913
std[9] = "Jack Seaton"
stdN[9] = 5426952637786535047257890165585593124886781517400739698793532459288242788641259859136937417543059411162316671230649974060640340281907685674054005689551173109247516043554034506218137083677742223513019113
stdE[9] = 12755321274062892471104436382361602100357499081718653818849784857975599364465852732174459833676075936561984537604556810508872381753208192558604476104319149952700485498756574436417118333473846564513
std[10] = "Brendon Sida"
stdN[10] = 2164700491961546656598967855994856214141952340596599142651378779558706584904423742280040379976928203762487166334835991729934850553260460460653965847360703362403989228228122224139869699071541459850580419
stdE[10] = 24525124702054761802824283935894849918735817024963555698709262481098389774736037620011058277354675413
std[11] = "Chris Collins"
stdN[11] = 4529650941907032867212055034880078910075722789709381126563121689410484136667555932854899898099936609023489522864262991302638183079738954169133045128068091122254285118846307685888073394880913836637081363
stdE[11] = 549085739485739485732390485739947345890734905834095802897128971259823475928572389572987020202897257045783999
std[12] = "Eric Lafferty"
stdN[12] = 701329861648443192697224548047440658836107304537383898688466041549232556968707194164836970170939483980365261293123894953654744094279407453098474938054077406870669236148955241032919440170714707579181691
stdE[12] = 93841
std[13] = "Jared Mart"
stdN[13] = 1143838779666368584525242249317835576110715765174059659261305688983057022313001021599547249166409022902980612678702634901707517996070402407828306968162033564665465494089115413120118128802422573583932009
stdE[13] = 65537
std[14] = "Nicholas Norton"
stdN[14] = 2099943677072620037362569232564696682747800682855496558193324340171748145785076598646843525559179375965576142270829975283721188301124973830481990285703992165760760560215816541802773868754351237715520219
stdE[14] = 901
std[15] = "Kaycie Upson"
stdN[15] = 373309148338424684602937561276891356395289175177171389726607245187561987723430426562408144311289779449829328886532607417643362314282369778824922710169667662580413242941129673154046396453225745365328668317
stdE[15] = 201763542482645493305715872443343004860142009301078112584537103304613414323358103410924097933387593417323079416660861896027340764844292880891876568869729822430256857950318111871838442429174176274452061
std[16] = "Jake Douglas"
stdN[16] = 234055950401511201040523187503739247775230701529428432806146687630184980805542705944315210478224503301370258025540967175160331674868770834217601404633032448946012736133008423443706584935577868163896929
stdE[16] = 35083947524977380582732392936628607469686627129482070423725565219141551158117961566083917508128639044377646368095569168012833513194661277626843007232493138311319058409089258972454567849284785089801139
std[17] = "Allison Sullivan"
stdN[17] = 6600339758942244848232410713340070523639647801183650929773078984695371649589598296528786566383914610227358760022351620512392703358613908739388609703160417267341788247185482335830947271923187895297293541
stdE[17] = 743500191101024353472347247865497967
std[18] = "Julian Vieyra"
stdN[18] = 2109943545100165864835121675039053448059599402351358425716774795292083956949573963756204535038574480948688708139647404455727033307061567811436279580637418302534071050204951628438005156690842158552773003
stdE[18] = 6265248020153
std[19] = "Ryleigh Moore"
stdN[19] = 1741172274375769440398621264526456974354771949025456484187731078876565034731596125744050373865338016292788366068131219007534289889322719590953163951967923883587875698207504723143189062372191944214319463
stdE[19] = 649072287502313
std[20] = "Aaron Gardner"
stdN[20] = 19012799666243633733525893518572652352125677558675098979266215750062494343606776519444548117930072447967702379358342760748066513353702856633014411516234382681190215329162259220558017914616666056429861
stdE[20] = 9506399833121816866762946759286326176062838779337549489633107875031247171803388259722274058965036218432306465292772581714571197711386980895134350401080176853432947958636808272845971738464318367025201
std[21] = "Michael Smith"
stdN[21] = 2761026094480286181173022779068979222239394966426607884297738055756299345866593113472845146454984581533128671591715906623952856862888299987559736186483607525354798075775339442155029109784071866870670103
stdE[21] = 5728126489271994775593210286582976082674930104876892028475936582909
std[22] = "Lindsey Gentry"
stdN[22] = 661236234632430768011476853090205989108882004575402802672984780985500576398994526956137663614569102729449117341193094376173974414095345864390097859366992491623706297328969413637456601710968624681173877
stdE[22] = 35415498421510406549065471984065719837
std[23] = "Ashley Rausch"
stdN[23] = 1025178058248146386842659121480422729149176138388911424091236136067372742371528354192874181117339982548348893128012116416631431852162759281503440052782171990408223389079780769700266230832743455565501087
stdE[23] = 1263525728987980721409782134789012978012345678965483765364758697
std[24] = "Rob Huelsenbeck"
stdN[24] = 2985215697063667337027837967833690245771636884782294429302040310060994675859748960416012996783081662518261899482133619578634488032546027165900195364991444954438832626159655227287737146041759917920944563
stdE[24] = 2947560163843856176311843371120697857461185744837211
std[25] = "Kyle Unruh"
stdN[25] = 1081683190927063793328723020182124371398283967855040235422817239850566250643227742438537752148859458942336231417623518198108787554313071440783591066660087623661613972097103651404433922354195446310691837
stdE[25] = 3961866063798696439193236106105057887477866611483608290968425099042625274025872641016397885606641248103118369363295529520825006644411369966929922774507422875431696965033937769020503455453
std[26] = "John Lewis"
stdN[26] = 1221702831040241240684070655908552491153520562070257453027816798084697791020050897141527477267589725192358849401060689182334661211174979126091654156137376957561621754302374552005914471558155007081134461
stdE[26] = 13
std[27] = "Joseph Carmona"
stdN[27] = 791321120760181354142088106418378464807936281169573932736519662664698094662373484989359456190473318898342131955920334445869863415641820824968168450326212983306972201053445886708760550870210158974650147
stdE[27] = 743345972349752340975457843759373945767
std[28] = "Eldin Turulja"
stdN[28] = 1275306274873872326572177496483600731851413819422845800179292666769959044693106783496729065944435543275543750889184501806019382831216528599408440793278070787675044791974511737054437244545473343725089259
stdE[28] = 62135126827394841923857198367918346819153648923437900165010436909487116430637569505620166561
std[29] = "Vanessa Komperda"
stdN[29] = 4553869130371551321418341328167960700950420899466169182646518685582760070246605155934230188431842474782578462493956373367938027400538869777191325229764014779031962028554532839498415350936908084272311723
stdE[29] = 77
std[30] = "Kalli Plumer"
stdN[30] = 906076157999561220838502301265792896495596174805403610206621377406281150964822969463621282959801704364208064565652677018755768788952954082520791627774717045360105685869729564409788469557865598314987359
stdE[30] = 6020219790006212790907095225161277755833659170693535727213856600909583926385218141228784694749164923
std[31] = "Jay Capcha"
stdN[31] = 1985953957858508530575619761984103116149571259055254722252904911688834130941020511002230321014428085188724536706845832162573509203677573795519286197767606631519647068882320246564892545833823201235438179
stdE[31] = 65537
std[32] = "Matthew Crosby"
stdN[32] = 4264291558194328373598895817740246275434190176702019733277188184751125299170265723596542299606408703273427726593101272639154596805249908932872512068274908330808038712509395275313314956000304733808637607
stdE[32] = 65537
std[33] = "Brandon Quirarte"
stdN[33] = 1295601491779745180817740752746641841944945206872368789696072472935543195735976736501866119670772541111690560237297164860002074812668948530347527382212760630255344075814886636715074599222403655770394303
stdE[33] = 65537
std[34] = "Cameron Wright"
stdN[34] = 1479398484588921844119968065110561657481812966078844734607364314754410487897476771477080753039078175013790288373278029862771794192929506873817090272452679151061608534467435313105397999532108085756690757
stdE[34] = 70816162146952118002542153504835578448238829162466895954985189513111517756974226191501817479054753929
std[35] = "Alyssa Seideman"
stdN[35] = 1009865690350861365796710251766676469588633172682526708764214124362951332686860013352527925284153875736480608963801676163074468038986363864143004986935361510177249891115320299642146951981782506723233697
stdE[35] = 209089863724868137492809183489984091843849031841316237198492089314810129

##Try to factor all encryption moduli
#for i in range (0,36):
#    x = FermatAttack(stdN[i],10000)
#    if x > 0:
#        print "Fermat Attack successful on",std[i],"'s modulus, factor found is", x
#    else:
#        x = RhoAttack(stdN[i],2000000)
#        if x > 0:
#            print "Rho Attack successful on",std[i],"'s modulus, factor found is", x
#        else:
#           x = ISAttack(stdN[i])
#            if x > 0:
#                print "IS Attack successful on",std[i],"'s modulus, factor found is", x
#            else:
#                print "Trying simple Sage factor() Attack on",std[i],"'s modulus"
#                x = factor(stdN[i])
#                if x[0] > 0:
#                    print "factor() successful on",std[i],"'s modulus, factor found is", x[0]





###Problem 2

##8 friends and their keys
friends = [0] * 8
friendsN = [0] * 8
friendsE = [0] * 8
friendsP = [0] * 8
friendsG = [0] * 8
friendsB = [0] * 8

friends[0] = "Alice"
friendsN[0] = 613374693673894523440764363117206767722757644446212481302567190250330348500582139857604394741360645339268135625505455043
friendsE[0] = 7
friendsP[0] = 7339893940555892950021117953932742794751344995120378281984000000000001
friendsG[0] = 89
friendsB[0] = 5045559467245388806919544662173483270575303492566631263887385366510885

friends[1] = "Bob"
friendsN[1] = 35803164849885939144143515500432851680614347095005681600310785168881135598916087713903687074477265501509137227413683450777
friendsE[1] = 7
friendsP[1] = 7339893940555892950021117953932742794751344995120378281984000000000001
friendsG[1] = 89
friendsB[1] = 3123683569755989820985993190223311739014013308415293162998048740001792

friends[2] = "Carlos"
friendsN[2] = 3806742363450025153123577082495302766807622721330374482400000003792467079587087558799363668435945381432094136125385578091
friendsE[2] = 7
friendsP[2] = 7339893940555892950021117953932742794751344995120378281984000000000001
friendsG[2] = 89
friendsB[2] = 7196639312013837610179196720728013256989179668060812392099401332127303

friends[3] = "Dimitar"
friendsN[3] = 6914798416321084535808517487261915062533861769484854940300000001076732896255711734861612008730783916880272761248355983561
friendsE[3] = 7
friendsP[3] = 66183000582500969135881095361760087711495414577990271277164204159664137
friendsG[3] = 10
friendsB[3] = 38583243400956506769381714470147374202627708403465461613562440969114782

friends[4] = "Elena"
friendsN[4] = 746635461604503245427986900797692536760356289696779377370288913481011097640877023286532191995788857118131613409728578917
friendsE[4] = 7
friendsP[4] = 42910149190942143400123458807606804030854016894549903802368000000000001
friendsG[4] = 107
friendsB[4] = 35670645011951373149226509955258365400309769263765763578182983795691462

friends[5] = "Francis"
friendsN[5] = 28431582191836036090015962313749700616208499447119837653386058085774321243354960253710501548225837244404799382926686946113
friendsE[5] = 7
friendsP[5] = 7339893940555892950021117953932742794751344995120378281984000000000001
friendsG[5] = 89
friendsB[5] = 6359809522508005484478156122692897777648975834633762264697088029017891

friends[6] = "Goran"
friendsN[6] = 2202282442655379733610562609070215383016798538657326700700000000342926837499194844233644749126647823926901486733783729109
friendsE[6] = 7
friendsP[6] = 63210641746359098914712106896114979212372803915809197337032425193078807
friendsG[6] = 5
friendsB[6] = 36071840592489603317558302173773322064104800865333946463833572645701478

friends[7] = "Henry"
friendsN[7] = 37709148143570068561906751922216529891977277651194139432321538744688458498485471030896198313062506300931802217086906794761
friendsE[7] = 7
friendsP[7] = 7339893940555892950021117953932742794751344995120378281984000000000001
friendsG[7] = 89
friendsB[7] = 7074067005393582120066451463371809711131668541136744206980261237371224

##10 messages between the 8 friends
M = [0] * 10
y = [0] * 10
s = [0] * 10
M[0] = 3950602632488857422305606215905720614672671463365747749232116250864932040237647120635751412111259462946151574728070004846
y[0] = 1535467970492676961616165462473953610213961813460693737172399936531744
s[0] = 3162327525533273277922555663101514586211164239746159340371333802796550
M[1] = 369085282845659793952944676626123765901727400303922569723229958526509668589177295586374127702816963807100470407451946792
y[1] = 1975821540706957177787827678185626085244421406332568635665362965770671
s[1] = 4852824158635684034390125066416222562285578680901234593619453144340895
M[2] = 16193710005369193740750988231435875547804782286135700495577612393063300489838261347881003113853095182293895263970168590391
y[2] = 5112416838627377949939081998476709479869322867452016315269715371437083
s[2] = 17894559309015393993581562351043999105451444783468243523729004876259039
M[3] = 593379064404571390792725990770135623028394582093240025095257008995488635113023806303243755175303677294205107456437799095
y[3] = 5842696547270625397038357321699646078999540069577472733256953004730268
s[3] = 7010974236749868003695795096936947594039155115088512454546561600029030
M[4] = 15501433062995352970442422112476444997172523428367777460156066075354756647508353103088016529039032067135197020936072133180
y[4] = 3877081433298579679997603102033339194816489449844706716792644380388518
s[4] = 4940443366058353508913694572541888012349655317503329839630286118559568
M[5] = 922641537255177722516656196532544718713578305612351186079856479865965365374003599791361357099555385059037512443049753843
y[5] = 3372434206192843627732412766365708961524949134049258396219805931974639
s[5] = 4753179596966279146793372215135321400646791849614448570110631003528275
M[6] = 2055202426636114589149631567158649701918620001469894929364119613317291143611281608415602660460512802099148536837844306024
y[6] = 351088503876582741609019128431805607832308942329362021003049295673118
s[6] = 1928343874986791357340345379587041665532608617380400874753401166752520
M[7] = 273009811859211198168676563350237987661745979069647509676280241239567945341659342238063740866604829848419180006569981176
y[7] = 28307706007500388727858788217928338672033646073317379589363173006608565
s[7] = 52275073063827463180975793799030602588927479979646337024604192121539515
M[8] = 816655722545207429045298458933572946450355569475360600321124298192450119604459857951683801335225751438462893950977492542
y[8] = 4648323384747839888984249439840080905480181476240631263794258259718963
s[8] = 7064629456035142188741282237046968931325170890308191479684956497818155
M[9] = 14680393536721035644748313943459782750493800101875031698109460955403158067489775368285137952538147875442601417790244864297
y[9] = 36184470669473917339558160049641155713038533089590895383541769647167478
s[9] = 16780565265847093864884686610785972686778364323862391790003095372591968

pFriends = [0] * 8 #Factors of the moduli of the friends
qFriends = [0] * 8
facMethod = [0] * 8 #Method used to find factor

phiNfriends = [0] * 8 #totient value for each persons key
dFriends = [0] * 8 #each person's private key

##Factor all encryption moduli
print "\n======================================================================================================================================================"
print "Beginning to factorize all moduli...\n"
for i in range (0,8):
    print "Trying Fermat Attack on",friends[i],"'s modulus"
    x = FermatAttack(friendsN[i],100)
    if x > 0:
        facMethod[i] = "Fermat Attack"
        print "Fermat Attack successful on",friends[i],"'s modulus, factor found is", x
    else:
        print "Trying Rho Attack on",friends[i],"'s modulus"
        x = RhoAttack(friendsN[i],20000)
        if x > 0:
            facMethod[i] = "Rho Attack"
            print "Rho Attack successful on",friends[i],"'s modulus, factor found is", x
        else:
            print "Trying IS Attack on",friends[i],"'s modulus"
            x = ISAttack(friendsN[i])
            if x > 0:
                facMethod[i] = "IS Attack"
                print "IS Attack successful on",friends[i],"'s modulus, factor found is", x
            else:
                 x = 0
    if x != 0:
        pFriends[i] = x
        qFriends[i] = friendsN[i]/x
print "\nAll Fermat, Rho, and IS Attacks completed, factors found have been stored\n"

##Try to find if any moduli share a common factor
print "\nTrying to find common prime factors\n"
for j in range (0,8):
    for k in range (0,8):
        if j != k:
            x = gcd(friendsN[j],friendsN[k])
            if x != 1:
                print "Common prime factor shared between",friends[j],"and",friends[k]
                facMethod[j] = "Common Factor"
                qFriends[j] = x
                pFriends[j] = friendsN[j]/x

##Verify that the discovered factors do infact multiply to form modulus
for i in range (0,8):
    if pFriends[i]*qFriends[i] != friendsN[i]:
        print "Factors are not valid"

##Print out the factorization of each friends modulus
print "\n======================================================================================================================================================"
print "Factorization of Each Person's Modulus\n"
print "Person\t\tFactoring Method\tp\t\t\t\t\t\t\t\t\tq\n"
for i in range (0,8):
    print friends[i],"    \t",facMethod[i],"\t\t",pFriends[i],"\t\t",qFriends[i]

##find each person's private RSA key
print "\n======================================================================================================================================================"
print "Private RSA Key of Each Person\n"
print "Person\t\tPrivate Key\n"
for i in range (0,8):
    phiNfriends[i] = euler_phi(pFriends[i]) * euler_phi(qFriends[i])
    dFriends[i] = (1/friendsE[i]) % phiNfriends[i]
    print friends[i],"    \t",dFriends[i]

##Decrypt all of the messages
#print "\n======================================================================================================================================================"
#print "All 10 Decrypted Messages\n"
decryptedMsgs = [0] * 10 #the 10 decrypted messages
paddedDecrMsgs = [0] * 10 #the 10 decrypted messages still in padded ASCII form
MsgSender = [0] * 10 #the person who sent the message
MsgRecipient = [0] * 10 #the person who got the message
for i in range (0,10):
    for j in range (0,8):
        decryptedMsg = decrypt(M[i],dFriends[j],friendsN[j])
        if decryptedMsg != "This is not a padded ASCII string\n":
            decryptedMsgs[i] = decryptedMsg
            paddedDecrMsgs[i] = decryptNoPad(M[i],dFriends[j],friendsN[j])
            MsgRecipient[i] = friends[j]
            #print "Message",i, "was sent to",MsgRecipient[i], "and decrypts to:",decryptedMsgs[i]

## Verify the messages so that the sender can be discovered
#print "\n======================================================================================================================================================"
#print "Signature Verification of the 10 Messages\n"
for i in range (0,10):
    for j in range (0,8):
        isValid = ElGamalVerify(paddedDecrMsgs[i],y[i],s[i], friendsG[j],friendsB[j],friendsP[j])
        if isValid == "Signature is Valid":
            MsgSender[i] = friends[j]
            #print "Message",i,"was sent from and signed by:",MsgSender[i]

##Print out message sender, recipient, and contents in tabular form
print "\n======================================================================================================================================================"
print "Message Information\n"
print "Message Number\tSent To\t\tSent From\tContents\n"
for i in range (0,10):
    decMsgNoNL = decryptedMsgs[i] #Get rid of the newline character in each message to make table look nicer
    decMsgNoNL = decMsgNoNL[:-1]
    print i,"\t\t",MsgRecipient[i],"    \t",MsgSender[i],"    \t",decMsgNoNL

##Determine as many El Gamal private keys as possible
print "\n======================================================================================================================================================"
print "Trying to Find as Many El Gamal Private Keys as Possible\n"
friendsX = [0] * 8 #private El Gamal Keys
discMethod = [0] * 8 #method of discovery of the private keys

for i in range (0,8):
#    print "Trying Baby Step Giant Step Attack on",friends[i],"'s EG key"
#    xx = BSGB(friendsG[i],friendsB[i],friendsP[i])
#    if xx > 0:
#        discMethod[i] = "BSGS Attack"
#        friendsX[i] = xx
#    else:
        print "Trying HPS Attack on",friends[i],"'s EG key"
        xx = HPSonP(friendsG[i],friendsB[i],friendsP[i])
        if  xx == "NO DATA (timed out)":
            discMethod[i] = "None"
            friendsX[i] = "The key was unable to be found, HPS Attack took too long\t"
        elif xx > 0:
            #print "HPS Attack was Successful, private key found was:",xx
            discMethod[i] = "HPS Attack"
            friendsX[i] = xx

##Check to see if the private keys found are correct
print "\nTesting the keys that were found for correctness\n"
for i in range (0,8):
    if friendsX[i] != "The key was unable to be found, HPS Attack took too long\t":
        print "Testing",friends[i],"'s private key for correctness"
        if power_mod(friendsG[i],friendsX[i],friendsP[i]) != friendsB[i]:
            print "Private key found is wrong!"
    else:
        print friends[i],"'s private key cant be tested, it was not found"

##Print out results in tabular form
print "\n======================================================================================================================================================"
print "\nEl Gamal Private Signature Keys\n"
print "Key Owner\tKey Value\t\t\t\t\t\t\t\tMethod of Discovery\n"
for i in range (0,8):
    print friends[i],"    \t",friendsX[i],"\t",discMethod[i]

##Try to find as many random numbers (r) used in signature as possible
print "\n======================================================================================================================================================"
print "Trying to find as many of the random numbers (r) used in the valid El-Gamal signatures as possible\n"
r = [0] * 10 # the random numbers used in signature
for i in range (0,10):
    try:
        M = paddedDecrMsgs[i]
#        print "Padded message:",M
        index = friends.index(MsgSender[i])                   #get the index of the person who signed this message so we can use the right x and p
        x = friendsX[index]                                   #Get the appropriate private key to use
#        print "Using",friends[index],"'s private key:",x
        p = friendsP[index]                                   #Get the appropriate P to use
#        print "Using",friends[index],"'s modulus:",p
#        print "Using this y:",y[i]
#        print "Using this s:",s[i]
        r[i] = (M-x*y[i])/s[i] % (p-1)
#        print "Random number found for msg",i,":",r[i],"\n"
        if s[i] != (M-x*y[i])/r[i] % (p-1):                    #Check to see if the number is right
            print "Random number found is not right!"
    except (OverflowError):
        r[i] = "Cannot be Found"
        continue

##Print out results in tabular form
print "\nRandom Numbers (r) used in the valid El-Gamal Signatures\n"
print "Message Number\tMessage Signer\t\tRandom Number\n"
for i in range (0,10):
    print i,"\t\t",MsgSender[i],"    \t\t",r[i]