bad_pedersen_commitment.py

"""
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
"""