CoCalc Public FilesPartial Key.sagews
Author: Liljana Babinkostova
Views : 143
Compute Environment: Ubuntu 20.04 (Default)

# Partial Key Exposure Attack

Description. This attack takes as input the modulus R, encryption exponent s, and the least significant digits of the private key partd. The output is either the full private key or in the case when the attack is not successful, the output is "not enough digits to discover d".


def partial (R, s, partd):
m = 1000
E = m.powermod(s,R)
for k in range(1, s + 1):
Dk = math.floor((k * (R - 2 * isqrt(R) + 1) + 1) / s)
l=(partd).ndigits()
Dk=Dk-(Dk % 10^l)+partd
mm = E.powermod(Dk,R)
if m == mm:
return(Dk)
print("Not enough digits to discover the private key")


Example. The following is an example when the number of digits of the partial key are not enough to discover the private key.

R=1030794365305576815134103206958049837943419896523;
s=17873;
partialD=681690773553162835501410052681017;
partial(R,s,partialD)

Not enough digits to discover the private key

Example. The following is an example when the number of digits of the partial key enough to discover the private key.

R =18089869975478455841816757989817115449865321
s = 7
partialD = 90721490913495888287004416695
Dd=partial(R,s,partialD);
print("The private key is",Dd)


The private key is 15505602836124390721490913495888287004416695