kangaroo 0.1.0

Pollard's Kangaroo ECDLP solver for secp256k1 using Vulkan/Metal/DX12 compute
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

//! 256-bit arithmetic utilities for kangaroo algorithm.

/// Add two 256-bit values (little-endian bytes).
#[allow(dead_code)]
pub fn add_256(a: &[u8], b: &[u8], result: &mut [u8]) {
    debug_assert!(a.len() >= 32 && b.len() >= 32 && result.len() >= 32);

    let mut carry = 0u16;
    for i in 0..32 {
        let sum = u16::from(a[i]) + u16::from(b[i]) + carry;
        result[i] = sum as u8;
        carry = sum >> 8;
    }
}

/// Subtract two 256-bit values: result = a - b (little-endian bytes).
#[allow(dead_code)]
pub fn subtract_256(a: &[u8], b: &[u8], result: &mut [u8]) {
    debug_assert!(a.len() >= 32 && b.len() >= 32 && result.len() >= 32);

    let mut borrow = 0i16;
    for i in 0..32 {
        let diff = i16::from(a[i]) - i16::from(b[i]) - borrow;
        if diff < 0 {
            result[i] = (diff + 256) as u8;
            borrow = 1;
        } else {
            result[i] = diff as u8;
            borrow = 0;
        }
    }
}

/// Negate a 256-bit value using two's complement.
/// Returns -value mod 2^256 (big-endian input/output).
pub fn negate_256_be(bytes: &[u8; 32]) -> [u8; 32] {
    let mut result = [0u8; 32];
    let mut carry = 1u16;

    // Two's complement: invert all bits and add 1
    // Process big-endian: index 31 is least significant
    for i in 0..32 {
        let idx = 31 - i;
        let inverted = !bytes[idx];
        let sum = inverted as u16 + carry;
        result[idx] = sum as u8;
        carry = sum >> 8;
    }

    result
}

/// Create DP mask with `dp_bits` trailing zeros required.
/// Returns mask in little-endian [u32; 8] format.
pub fn create_dp_mask(dp_bits: u32) -> [u32; 8] {
    let mut mask = [0u32; 8];

    let full_limbs = (dp_bits / 32) as usize;
    let remaining_bits = dp_bits % 32;

    // Set full limbs from the bottom (index 0 up)
    for limb in mask.iter_mut().take(full_limbs.min(8)) {
        *limb = 0xFFFF_FFFF;
    }

    // Partial limb
    if remaining_bits > 0 && full_limbs < 8 {
        mask[full_limbs] = (1u32 << remaining_bits) - 1;
    }

    mask
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_add_256_simple() {
        let a = [1u8; 32];
        let b = [1u8; 32];
        let mut result = [0u8; 32];
        add_256(&a, &b, &mut result);
        assert_eq!(result[0], 2);
    }

    #[test]
    fn test_add_256_carry() {
        let mut a = [0u8; 32];
        a[0] = 0xFF;
        let mut b = [0u8; 32];
        b[0] = 0x01;
        let mut result = [0u8; 32];
        add_256(&a, &b, &mut result);
        assert_eq!(result[0], 0x00);
        assert_eq!(result[1], 0x01);
    }

    #[test]
    fn test_subtract_256_simple() {
        let mut a = [0u8; 32];
        a[0] = 5;
        let mut b = [0u8; 32];
        b[0] = 3;
        let mut result = [0u8; 32];
        subtract_256(&a, &b, &mut result);
        assert_eq!(result[0], 2);
    }

    #[test]
    fn test_subtract_256_borrow() {
        let mut a = [0u8; 32];
        a[1] = 1; // 256 in LE
        let mut b = [0u8; 32];
        b[0] = 1;
        let mut result = [0u8; 32];
        subtract_256(&a, &b, &mut result);
        assert_eq!(result[0], 0xFF);
        assert_eq!(result[1], 0x00);
    }

    #[test]
    fn test_negate_256_be() {
        // Negate 1 should give -1 (all 0xFF in two's complement)
        let mut one = [0u8; 32];
        one[31] = 1; // big-endian: LSB at end
        let neg = negate_256_be(&one);
        assert!(neg.iter().all(|&b| b == 0xFF));
    }

    #[test]
    fn test_create_dp_mask_8_bits() {
        let mask = create_dp_mask(8);
        assert_eq!(mask[0], 0xFF);
        assert_eq!(mask[1], 0);
    }

    #[test]
    fn test_create_dp_mask_32_bits() {
        let mask = create_dp_mask(32);
        assert_eq!(mask[0], 0xFFFF_FFFF);
        assert_eq!(mask[1], 0);
    }

    #[test]
    fn test_create_dp_mask_40_bits() {
        let mask = create_dp_mask(40);
        assert_eq!(mask[0], 0xFFFF_FFFF);
        assert_eq!(mask[1], 0xFF);
        assert_eq!(mask[2], 0);
    }
}