LegendreCovertChannel.sagews

%html
<h1><center>Legendre Covert Channel on ElGamal Signature</center></h1>

Legendre Covert Channel on ElGamal Signature

Description. We assume that the private key of at most 160 bits and we divide into 16 block with equal size (10 bits). Also, assume that the programmer is actually the adversary. They developed a software for El Gamal signature generation, but they also use 14 primes (chosen by the adversary) in their code. Four primes will be used to leak a block number and the rest of the primes (10 primes) will be used to leak the content of the block. The adversary needs at least 16 signatures in order to discover the key. The function 'KeyDiscover' takes as input a list of sixteen 'y' values (part of the signatures) and a list of primes (assumed to be chosen by the adversary). The procedure returns the private key leaked by the covert channel.

def NewLegendre(a,p):
    if is_prime(p):
        return (1+kronecker(a,p))/2
    else:
        print ("2nd argument has to be a prime")
        
def BlockNumber(y,primelist):
    m=0
    for i in range(0,4):
        m = 2*m + NewLegendre(y,primelist[i+10])
    return m+1

def BlockContents(y,primelist):
    k=0
    for i in range(0,10):
        k=10*k+NewLegendre(y,primelist[i])
    return k

def KeyDiscover(ylist,primelist):
    c=10^10
    k=0
    for i in range(16):
        d=16-BlockNumber(ylist[i],primelist)
        k=k+(BlockContents(ylist[i],primelist))*(c^d)
        #k=k+(BlockContents(ylist[i],primelist))*c^d
    return int(str(k),2)

Example. An example input of a list of 'y' signatures and 'prime' values that will be used to leak the key.

y=[0]*17
s=[0]*17
p=[0]*15
y[1]= 6355654156581339292380028178295946379397857230419335473049773634105011
s[1]= 3560725073968654220540577725166322807481561312157414571860157629465222


y[2]= 6157738735079726271974947267390448530039834693941568486254984166399169
s[2]= 6291144800430142601833562065314744488661843993287483337500999473866049



y[3]= 9335313663168312334842734241780762294755281133475486862667663109265693
s[3]= 1031174004049088397035651840893708758323829943237917442328886035203304


y[4]= 5666312454503499142803478855324287143700047631332918051757975784387852
s[4]= 7474462038392337038267162594316747902979250709302501061852809955557686



y[5]= 8609729555305475123927447895155480568383891784974360653476349663970219
s[5]= 9392131610200414588504854275564189165850448855170937440564772246654800



y[6]= 7365404439138911411864937298776875814102498525963049435105763372378772
s[6]= 647447785466753660592038806991306978403341150904526358877367886003642



y[7]= 5705440343386587753765002035968279773205391692599442025007820809081663
s[7]= 7706884617942615865555527903233116366329368354497449630894822636431727



y[8]= 9139181219517140532824520580591540432442737355121485514849816985670182
s[8]= 9119886852416426951627821313728462871487106020439368341742027870361688


y[9]= 3851953190357247351746340095276683473382065321260493360272121028908078
s[9]= 5799995345355474114152639857813718721964327387996505577731360092639224



y[10]= 8332119728236605996252741802820164399490394892793656670206410123540806
s[10]= 3382049014239536347193207790839121703028337382022833734591171852421851


y[11]= 1090916439028367923335435833686239225083325662650219511577614470087626
s[11]= 784467849834343142005625314726078169629151138271180139914842146743784



y[12]= 4044337428348522271547535017777415980322724356426081427629324943634693 
s[12]= 875430208213556723165929030182187434842223658973047200347756281547097


y[13]= 5047503978916103346914776520107614498353295441864520623517103573476005
s[13]= 8856726072244904117515011381053001354515613401207356043353782820904450



y[14]= 3079609686866100016134750688150613028636970390199280613932162055042282
s[14]= 2910381948910080172894739786204355803866267753930250967405306509357624



y[15]= 2507949926452818146783101167935559217583543852145717090862513023080430
s[15]= 2448150721429647913194335461249415499372183912050199930744663457020240


y[16]= 1137237284834714268920432440084126521105380025168123492652543171722168
s[16]= 9770021075461804348672365094369599228327792685910556392116440254449953


p[1]=2610874309742867231360502542308382199053675592825240788613991898567287
p[2]=6881793749340807728335795394301261629479870548736450984003401594706373
p[3]=8314906195914825136973281314862289454100745237769034410057080703111511
p[4]=5127114594552921209928891515242515620324828055912854227507525717981667
p[5]=7473570262981491527797413449568788992987500442157627511097882499376811
p[6]=9062890227065912603127119521589474574157513825150650905007553408748219
p[7]=2815984929359632269852681585809504709739738485231104248045693804710167
p[8]=8302655538010818866476054310788175542136407374106205605523687223947057
p[9]=5812242019121022573901665288968349097396414947780422731613987785640429
p[10]=4198272844134050365811754869582636140810856859347877704841433599229643
p[11]=8724880795485531802023255050614524952922474293642065329619154912668053
p[12]=6069438450681407641506962917791070874166946435905950292905549552889463
p[13]=4125842236067060541266621757734462223575905687273574099511410424381497
p[14]=9501247275887974857856234450269247606386273485070460241146322057229349

ylist = [0]*16  
for i in range(16):
    ylist[i]=y[i+1]
    y[i]=y[i+1]
    s[i]=s[i+1]
print (ylist)

primelist = [0]*14
for i in range(14):
    primelist[i]=p[i+1]
for i in range(14):
    p[i]=p[i+1]
    primelist[i]=p[i+1]
print (primelist)

[6355654156581339292380028178295946379397857230419335473049773634105011, 6157738735079726271974947267390448530039834693941568486254984166399169, 9335313663168312334842734241780762294755281133475486862667663109265693, 5666312454503499142803478855324287143700047631332918051757975784387852, 8609729555305475123927447895155480568383891784974360653476349663970219, 7365404439138911411864937298776875814102498525963049435105763372378772, 5705440343386587753765002035968279773205391692599442025007820809081663, 9139181219517140532824520580591540432442737355121485514849816985670182, 3851953190357247351746340095276683473382065321260493360272121028908078, 8332119728236605996252741802820164399490394892793656670206410123540806, 1090916439028367923335435833686239225083325662650219511577614470087626, 4044337428348522271547535017777415980322724356426081427629324943634693, 5047503978916103346914776520107614498353295441864520623517103573476005, 3079609686866100016134750688150613028636970390199280613932162055042282, 2507949926452818146783101167935559217583543852145717090862513023080430, 1137237284834714268920432440084126521105380025168123492652543171722168] [2610874309742867231360502542308382199053675592825240788613991898567287, 6881793749340807728335795394301261629479870548736450984003401594706373, 8314906195914825136973281314862289454100745237769034410057080703111511, 5127114594552921209928891515242515620324828055912854227507525717981667, 7473570262981491527797413449568788992987500442157627511097882499376811, 9062890227065912603127119521589474574157513825150650905007553408748219, 2815984929359632269852681585809504709739738485231104248045693804710167, 8302655538010818866476054310788175542136407374106205605523687223947057, 5812242019121022573901665288968349097396414947780422731613987785640429, 4198272844134050365811754869582636140810856859347877704841433599229643, 8724880795485531802023255050614524952922474293642065329619154912668053, 6069438450681407641506962917791070874166946435905950292905549552889463, 4125842236067060541266621757734462223575905687273574099511410424381497, 9501247275887974857856234450269247606386273485070460241146322057229349]

Example.
This code snippet below shows the execution of the 'KeyDiscover' function that takes as input the list of primes and y valeus and returns the full leaked 160-bit key in integer format.

x = KeyDiscover(y,p)
print ("The private key is", x)

The private key is 1290003348882681184907543014445365590610205625395