Skip to content

Instantly share code, notes, and snippets.

@GiacomoPope
Last active November 10, 2021 20:03
Show Gist options
  • Save GiacomoPope/9f42c47b81c6fe12bb00a09037920e8c to your computer and use it in GitHub Desktop.
Save GiacomoPope/9f42c47b81c6fe12bb00a09037920e8c to your computer and use it in GitHub Desktop.
"""
Written to help twitter user @mukesh_tiwari
understand
https://asecuritysite.com/zero/ped
This implementation however is broken, as
q is not a prime...
Below is showing how we can sign a message m2 which
matches the commit c when the secret s is known.
"""
s = 127061960318157441305611619210305381385243836289
p = 1221610829295564460723761744864842608773486955679
q = 2443221658591128921447523489729685217546973911359
g = 302920252669257423408378018077544777649429799815
h = 1439586647863202107428388104356554654139305524847
m1 = 13
m2 = 70
c1, r1 = 1651892612201128691454158359728067134653772212614 , 622707043596099371743544902469500971046639421047
# This is the standard commitment scheme
c_check = pow(g,m1,q) * pow(h, r1, q) % q
assert c_check == c1
# Think as a power of g
c_test = pow(g, m1 + s*r1, q)
assert c_test == c1
# q is not prime, so we cant use (q-1) for this
# Not sure what the order of g is, but we know the
# order must divide phi(q)
# In proper specification, g is order q and we work mod p
phi_q = 2376594788792168432851531533522782759465848922112
# We can then sign any message m to match c by controlling r
r_forged = (s*r1 + m1 - m2) * pow(s,-1,phi_q) % phi_q
c_forged = pow(g, m2 + s*r_forged, q)
# Appendix
"""
I was lazy and used sage for to compute the totient, but
for anyone worried about the value I used:
sage: q = 2443221658591128921447523489729685217546973911359
sage: assert not is_prime(q)
sage: factor(q)
37 * 4003 * 10431396497 * 1581368567744562157485263641968577
sage: euler_phi(q)
2376594788792168432851531533522782759465848922112
"""
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment