2
$\begingroup$

I'm trying to implement kleptography SETUP attack of ecdsa with python. Just a simply script to verify the algorithm. However i can't get the right output as the paper said. Where is the problem? Can anyone help?

The algorithm

from ecpy.curves import Curve, Point
import hashlib
import gmpy

cv = Curve.get_curve('secp256k1')
G = Point(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
          0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8,
          cv)


def sign(k, d, hash):
    R = k * G
    r1 = R.x % p
    k_ = int(gmpy.invert(k, p))
    s1 = (k_ * (hash + d * r1)) % p
    return (r1, s1)


(a, b, h, e) = (11, 22, 33, 44)
hash1 = 987654321
hash2 = 77777
d = 123
v = 456
p = 2 ** 256 - 2 ** 32 - 977
j = 0
u = 1

pKey1 = d * G
V = v * G

k1 = 8888
(r1, s1) = sign(k1, d, hash1)
print("(r1, s1): ", (r1, s1))

z = a * k1 * G + b * k1 * V + h * j * G + e * u * V
k2 = hashlib.sha256(str(z).encode('ASCII')).digest()
k2 = int.from_bytes(k2, 'big')
(r2, s2) = sign(k2, v, hash2)
print("(r2, s2): ", (r2, s2))

R1 = Point(x=r1, y=(cv.y_recover(x=r1)), curve=cv)
Z1 = a * R1 + b * v * R1
Z2 = Z1 + h * j * G + e * u * V
K2 = int.from_bytes(hashlib.sha256(str(Z2).encode('ASCII')).digest(), 'big')
print(K2 * G.x)
$\endgroup$
0
$\begingroup$

Never mind. Just implemented it in rust-lang. And this is my code. Just simply implemented. Need further work & don't take it seriously

use curv::arithmetic::Converter;
use curv::elliptic::curves::{ Point, Scalar, Secp256k1};
use curv::BigInt;
use openssl::hash::{Hasher, MessageDigest};

fn main() {
    let mut hasher = Hasher::new(MessageDigest::sha256()).unwrap();

    // Attacker's private key
    let v = Scalar::<Secp256k1>::random();
    // Attacker's public key
    let V = Point::generator() * v.clone();

    // User's private key
    let D = Scalar::<Secp256k1>::random();
    println!("{:?}", D.to_bigint());
    // User's public key
    let Q = Point::generator() * D.clone();

    let message1 = String::from("First message to sign");
    let message2 = String::from("Second message to sign");

    hasher.update(message1.as_bytes()).expect("Hash error");
    let m1: Scalar<Secp256k1> =
        Scalar::from_bigint(&(BigInt::from_bytes(hasher.finish().unwrap().as_ref())));

    let k1 = Scalar::<Secp256k1>::random();
    let signaturePoint1 = Point::generator() * k1.clone();
    let r1 = Scalar::from_bigint(&(signaturePoint1.x_coord().unwrap()));
    let s1 = k1.clone().invert().unwrap() * (m1.clone() + D.clone() * r1.clone());

    println!("r1: {:?}", r1.to_bigint());
    println!("s1: {:?}", s1.to_bigint());

    hasher.update(message2.as_bytes()).expect("Hash error");
    let m2: Scalar<Secp256k1> =
        Scalar::from_bigint(&(BigInt::from_bytes(hasher.finish().unwrap().as_ref())));

    let a: Scalar<Secp256k1> = Scalar::random();
    let b: Scalar<Secp256k1> = Scalar::random();
    let h: Scalar<Secp256k1> = Scalar::random();
    let e: Scalar<Secp256k1> = Scalar::random();
    let u: Scalar<Secp256k1> = Scalar::from(0 as u16);
    let j: Scalar<Secp256k1> = Scalar::from(0 as u16);

    let Z = a.clone() * k1.clone() * Point::generator()
        + b.clone() * k1.clone() * V.clone()
        + j.clone() * h.clone() * Point::generator()
        + u.clone() * e.clone() * V.clone();
    let zX = Z.x_coord().unwrap();
    hasher.update(&zX.to_bytes()).expect("Hash error");
    let hash =
        Scalar::<Secp256k1>::from_bigint(&(BigInt::from_bytes(hasher.finish().unwrap().as_ref())));
    let k2 = hash;
    let signaturePoint2 = k2.clone() * Point::generator();
    let r2 = Scalar::<Secp256k1>::from_bigint(&signaturePoint2.x_coord().unwrap());
    let s2 = k2.clone().invert().unwrap() * (m2.clone() + r2.clone() * D.clone());
    println!("r2: {:?}", r2.to_bigint());
    println!("s2: {:?}", s2.to_bigint());
    let recovered = ExtractUsersPrivateKey(message1, message2, a, b, h, e, r1, s1, r2, s2, v, V, Q);
    println!("{:?}", recovered.to_bigint());
}

fn ExtractUsersPrivateKey(
    message1: String,
    message2: String,
    a: Scalar<Secp256k1>,
    b: Scalar<Secp256k1>,
    h: Scalar<Secp256k1>,
    e: Scalar<Secp256k1>,
    r1: Scalar<Secp256k1>,
    s1: Scalar<Secp256k1>,
    r2: Scalar<Secp256k1>,
    s2: Scalar<Secp256k1>,
    attackerPrivate: Scalar<Secp256k1>,
    attackerPublic: Point<Secp256k1>,
    userPublic: Point<Secp256k1>,
) -> Scalar<Secp256k1> {
    let mut hasher = Hasher::new(MessageDigest::sha256()).unwrap();

    hasher.update(message1.as_bytes()).expect("Hash error");
    let m1: Scalar<Secp256k1> =
        Scalar::from_bigint(&(BigInt::from_bytes(hasher.finish().unwrap().as_ref())));

    hasher.update(message2.as_bytes()).expect("Hash error");
    let m2: Scalar<Secp256k1> =
        Scalar::from_bigint(&(BigInt::from_bytes(hasher.finish().unwrap().as_ref())));
    let w = s1.invert().unwrap();
    let u1 = m1.clone() * w.clone();
    let u2 = r1.clone() * w.clone();
    let verifyPoint = u1.clone() * Point::generator() + u2.clone() * userPublic.clone();

    let Z1 = verifyPoint.clone() * a.clone()
        + (verifyPoint.clone() * b.clone() * attackerPrivate.clone());

    let u: Scalar<Secp256k1> = Scalar::from(0 as u16);
    let j: Scalar<Secp256k1> = Scalar::from(0 as u16);
    let Z2 = Z1.clone()
        + j.clone() * h.clone() * Point::generator()
        + u.clone() * e.clone() * attackerPublic.clone();
    let zX: Scalar<Secp256k1> = Scalar::from_bigint(&Z2.x_coord().unwrap());
    hasher.update(&zX.to_bigint().to_bytes()).expect("Hash error");
    let hash: Scalar<Secp256k1> =
        Scalar::from_bigint(&BigInt::from_bytes(hasher.finish().unwrap().as_ref()));
    let kCandiate = hash.clone();
    let verifyPointCandiate = kCandiate.clone() * Point::generator();
    let rCandiate = verifyPointCandiate.x_coord().unwrap();
    if rCandiate == r2.to_bigint() {
        return (s2.clone() * kCandiate.clone() - m2) * (r2.invert().unwrap());
    }
    Scalar::random()
}

This is the library I'm using

[dependencies]
curv-kzen = "0.8"
openssl = "0.10"
openssl-sys = "0.9"
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.