Score:2

kleptography SETUP attack in ecdsa

de flag
Zim

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)
Score:0
de flag
Zim

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

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.