CoCalc Public FilesLegendreCovertChannel.sagews
Authors: Liljana Babinkostova, William Unger
Views : 284
Compute Environment: Ubuntu 20.04 (Default)
##############################################################################################################
# We want to discover a private key of at most 160 bits from signatures using a Legendre-type covert channel.#
# We have 14 covert primes, and 16 signatures which reveal 16 blocks of 10 bits each about the private key.  #
##############################################################################################################

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)

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 - This is the list of y's from the signatures given in the form ylist =[y1,y2,....,y16] #
# primelist - This is the list of coverts primes given in the order they appear in the program. #
# It is given in the form primelist =[prime1,prime2,....,prime10,prime11,...,prime14]           #
#################################################################################################

ylist = [0]*16  #Steps down indexing from 1-16 down to 0-15.
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]
len(primelist)
testout = KeyDiscover(y,p)
print (testout)


14 1290003348882681184907543014445365590610205625395
BlockNumber(y[0],p)

3



︠0ec075e3-14c2-45d5-a774-b718e6832aeds︠
BlockContents(ylist[0],p)

1100
for i in range(16):
bc = BlockContents(ylist[i],primelist)
print (BlockNumber(ylist[i],primelist),bc,)

3 1100 9 110011001 10 100100101 13 1011111110 5 11000100 15 1010010011 11 111110011 16 110011 14 1100110001 8 1100111010 7 111100111 4 1011100010 12 10100110 2 1101011100 6 1001011 1 1110000111