recrypt 0.16.0

A pure-Rust implementation of Transform Encryption, a Proxy Re-encryption scheme
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

#!/usr/bin/env python3
"""
Compute the 62-bit Montgomery limb representations for field.rs constants.

This script converts the 31-bit Montgomery limb constants to their 62-bit equivalents
by first reversing the Montgomery transformation to get the actual values, then
re-applying the Montgomery transformation with the new limb size.

The key insight is that Montgomery values in different limb formats represent the same
number but use different R values (where R = 2^(limb_size * num_limbs) mod p).
Simply repacking limbs doesn't work - you need to compute value = monty_value * R^-1 mod p
then convert back to Montgomery form with the new R.

Usage:
    python3 compute_field_constants.py
"""

# Fp256 prime
FP256_PRIME = 65000549695646603732796438742359905742825358107623003571877145026864184071783

# Fp480 prime
FP480_PRIME = 3121577065842246806003085452055281276803074876175537384188619957989004527066410274868798956582915008874704066849018213144375771284425395508176023

def to_limbs(n: int, limb_size: int, num_limbs: int) -> list:
    """Convert integer to limb representation"""
    mask = (1 << limb_size) - 1
    limbs = []
    for _ in range(num_limbs):
        limbs.append(n & mask)
        n >>= limb_size
    return limbs

def from_limbs(limbs: list, limb_size: int) -> int:
    """Convert limb representation to integer"""
    result = 0
    for i, limb in enumerate(limbs):
        result |= limb << (limb_size * i)
    return result

def to_montgomery(value: int, prime: int, limb_size: int, num_limbs: int) -> list:
    """Convert a value to Montgomery form and return limbs"""
    # R = 2^(limb_size * num_limbs)
    R = 1 << (limb_size * num_limbs)
    # Montgomery form: value * R mod prime
    montgomery_value = (value * R) % prime
    return to_limbs(montgomery_value, limb_size, num_limbs)

def from_31bit_monty_to_value(limbs31: list, prime: int) -> int:
    """Convert 31-bit Montgomery limbs back to the actual value"""
    num_limbs = len(limbs31)
    limb_size = 31
    R = 1 << (limb_size * num_limbs)
    R_inv = pow(R, -1, prime)  # modular inverse of R mod prime
    monty_value = from_limbs(limbs31, limb_size)
    return (monty_value * R_inv) % prime

def main():
    print("=== Fp256 ExtensionField constants ===\n")

    # All the 31-bit constants from field.rs for Fp256
    fp256_constants = {
        "xi_inv_times_9_elem1": [2050346385, 731299471, 959575992, 34915099, 1787054046, 707674376, 1189605443, 44293910, 138],
        "xi_inv_times_9_elem2": [729307778, 258461402, 1559141440, 1381403208, 157052610, 1802371594, 636365429, 127350700, 17],
        "frobenius_factor_1_elem1": [12717650, 1979656862, 1972108829, 1559171847, 290869350, 694266310, 579853055, 1597302116, 4],
        "frobenius_factor_1_elem2": [916222744, 723717387, 574787027, 1552331516, 1261698828, 887614939, 1510504974, 237248389, 8],
        "frobenius_factor_2_elem1": [15189756, 1959629061, 767155255, 1427131279, 513871136, 1996531885, 1401068065, 1422686260, 66],
        "frobenius_factor_2_elem2": [656635847, 1575335407, 606381995, 1750621660, 1486126693, 503904416, 1955368925, 270969940, 28],
        "frobenius_factor_fp12_elem1": [454717458, 161507933, 804946138, 817080316, 1413496639, 904558052, 1356825578, 765259087, 11],
        "frobenius_factor_fp12_elem2": [392395988, 386079276, 1435458002, 829532913, 1153717094, 1170750470, 311764801, 1868664732, 53],
        "twisted_curve_const_coeff_elem1": [1925150376, 516250914, 1051564560, 1369812449, 731601065, 672046428, 625168271, 1952553705, 93],
        "twisted_curve_const_coeff_elem2": [1674758358, 86153800, 1235541696, 1892123501, 768178752, 600790531, 1643777575, 1474105998, 5],
    }

    for name, limbs31 in fp256_constants.items():
        actual_value = from_31bit_monty_to_value(limbs31, FP256_PRIME)
        limbs62 = to_montgomery(actual_value, FP256_PRIME, 62, 5)
        print(f"// {name}")
        print(f"// actual value: {actual_value}")
        print(f"fp_256::Monty::new({limbs62}),")
        print()

    print("\n=== Fp480 ExtensionField constants ===\n")

    # All the 31-bit constants from field.rs for Fp480
    fp480_constants = {
        "xi_inv_times_9_elem1": [1671524251, 1452836661, 1514278714, 1089055752, 983710563, 1342902855, 1277558075, 1876974179, 947518822, 981090444, 247487949, 1283900828, 1334523677, 1392777601, 1513546415, 5235],
        "xi_inv_times_9_elem2": [335877574, 1323354927, 650625437, 272173725, 1832380438, 2065643415, 655409061, 1376608173, 1642768871, 464289801, 840813404, 665753910, 1051781983, 447188070, 183786362, 17059],
        "frobenius_factor_1_elem1": [1789717966, 1667803516, 415596737, 273473839, 86323342, 1847146047, 411641533, 883838890, 333532818, 2020025246, 1090726896, 1144837448, 1056047014, 650675300, 1518220857, 28583],
        "frobenius_factor_1_elem2": [1463808839, 1670428701, 447968177, 1822223094, 1576270537, 1038296259, 66655687, 578662642, 153246326, 1500216407, 53886423, 1315635309, 1456804263, 176996090, 1710325846, 31113],
        "frobenius_factor_2_elem1": [721025432, 530063334, 1045885399, 453726440, 2141696003, 1626330876, 1074975251, 1714081964, 1995410861, 609055642, 2058665923, 1876157870, 937690781, 1255299233, 741827240, 14111],
        "frobenius_factor_2_elem2": [147532118, 4451373, 893741577, 424324553, 481155820, 353715416, 620523272, 346497951, 1670022807, 1427377181, 732861676, 2088692375, 582789470, 669478976, 249410141, 28740],
        "frobenius_factor_fp12_elem1": [736041138, 285900164, 1852287620, 1099722104, 1782561133, 1457388007, 1874229037, 1965266811, 1231149838, 771491782, 467524787, 1737481601, 782773382, 79418783, 1572898018, 31139],
        "frobenius_factor_fp12_elem2": [492638839, 304045155, 1057698408, 772372983, 1813080623, 1701111681, 801357526, 1606643950, 1537923020, 1695901916, 157173875, 1177883133, 354458948, 163418612, 376825454, 23056],
        "twisted_curve_const_coeff_elem1": [1976657987, 2124705180, 1103755761, 1290923474, 2085255841, 1647224075, 1270424569, 286550022, 1158572853, 451253923, 1853842034, 2007948773, 1667592921, 2116284018, 790821013, 23589],
        "twisted_curve_const_coeff_elem2": [1531442428, 2081544602, 1531699218, 302801582, 1652317917, 456481830, 1063041565, 835589236, 1390322869, 278987042, 1335789303, 1086071918, 1573345690, 1085259625, 1063395545, 27530],
    }

    for name, limbs31 in fp480_constants.items():
        actual_value = from_31bit_monty_to_value(limbs31, FP480_PRIME)
        limbs62 = to_montgomery(actual_value, FP480_PRIME, 62, 8)
        print(f"// {name}")
        print(f"// actual value: {actual_value}")
        print(f"fp_480::Monty::new({limbs62}),")
        print()

if __name__ == "__main__":
    main()