0
# Mathematical Functions & Low-Level Operations
1
2
Low-level mathematical functions for elliptic curve cryptography, number theory operations, and deterministic signature generation. These functions provide the mathematical foundation for higher-level cryptographic operations.
3
4
## Capabilities
5
6
### Number Theory Functions
7
8
Mathematical operations on integers including modular arithmetic, primality testing, and specialized elliptic curve mathematical operations.
9
10
```python { .api }
11
def gcd(*a):
12
"""
13
Greatest common divisor of multiple numbers.
14
15
Parameters:
16
- a: int, numbers to find GCD of
17
18
Returns:
19
int, greatest common divisor
20
"""
21
22
def lcm2(a, b):
23
"""
24
Least common multiple of two numbers.
25
26
Parameters:
27
- a: int, first number
28
- b: int, second number
29
30
Returns:
31
int, least common multiple
32
"""
33
34
def lcm(*a):
35
"""
36
Least common multiple of multiple numbers.
37
38
Parameters:
39
- a: int, numbers to find LCM of
40
41
Returns:
42
int, least common multiple
43
"""
44
45
def jacobi(a, n):
46
"""
47
Compute Jacobi symbol (a/n).
48
49
Parameters:
50
- a: int, numerator of Jacobi symbol
51
- n: int, denominator (must be odd positive integer)
52
53
Returns:
54
int, Jacobi symbol value (-1, 0, or 1)
55
56
Raises:
57
JacobiError: if n is not odd positive integer
58
"""
59
60
def square_root_mod_prime(a, p):
61
"""
62
Compute square root of a modulo prime p.
63
64
Parameters:
65
- a: int, number to find square root of
66
- p: int, prime modulus
67
68
Returns:
69
int, square root of a mod p
70
71
Raises:
72
SquareRootError: if a is not a quadratic residue mod p
73
"""
74
75
def is_prime(n):
76
"""
77
Test if number is prime using Miller-Rabin test.
78
79
Parameters:
80
- n: int, number to test
81
82
Returns:
83
bool, True if n is prime
84
"""
85
86
def next_prime(starting_value):
87
"""
88
Find next prime number >= starting_value.
89
90
Parameters:
91
- starting_value: int, starting point for search
92
93
Returns:
94
int, next prime >= starting_value
95
"""
96
97
def factorization(n):
98
"""
99
Prime factorization of integer.
100
101
Parameters:
102
- n: int, number to factorize
103
104
Returns:
105
list[int], list of prime factors
106
"""
107
```
108
109
### Polynomial Operations
110
111
Functions for polynomial arithmetic over finite fields, used in elliptic curve operations.
112
113
```python { .api }
114
def polynomial_reduce_mod(poly, polymod, p):
115
"""
116
Reduce polynomial modulo another polynomial over GF(p).
117
118
Parameters:
119
- poly: list[int], polynomial coefficients
120
- polymod: list[int], modulus polynomial coefficients
121
- p: int, prime field characteristic
122
123
Returns:
124
list[int], reduced polynomial coefficients
125
"""
126
127
def polynomial_multiply_mod(m1, m2, polymod, p):
128
"""
129
Multiply polynomials modulo another polynomial over GF(p).
130
131
Parameters:
132
- m1: list[int], first polynomial coefficients
133
- m2: list[int], second polynomial coefficients
134
- polymod: list[int], modulus polynomial coefficients
135
- p: int, prime field characteristic
136
137
Returns:
138
list[int], product polynomial coefficients
139
"""
140
141
def polynomial_exp_mod(base, exponent, polymod, p):
142
"""
143
Exponentiate polynomial modulo another polynomial over GF(p).
144
145
Parameters:
146
- base: list[int], base polynomial coefficients
147
- exponent: int, exponent
148
- polymod: list[int], modulus polynomial coefficients
149
- p: int, prime field characteristic
150
151
Returns:
152
list[int], result polynomial coefficients
153
"""
154
```
155
156
### RFC 6979 Deterministic Signature Functions
157
158
Functions for generating deterministic k values per RFC 6979, ensuring signature determinism while maintaining security.
159
160
```python { .api }
161
def generate_k(order, secexp, hash_func, data, retry_gen=0, extra_entropy=b""):
162
"""
163
Generate deterministic k value per RFC 6979.
164
165
Parameters:
166
- order: int, curve order
167
- secexp: int, private key (secret exponent)
168
- hash_func: callable, hash function to use
169
- data: bytes, data being signed
170
- retry_gen: int, retry counter for different k values
171
- extra_entropy: bytes, additional entropy
172
173
Returns:
174
int, deterministic k value for signature
175
"""
176
177
def bits2int(data, qlen):
178
"""
179
Convert bit string to integer per RFC 6979.
180
181
Parameters:
182
- data: bytes, input bit string
183
- qlen: int, bit length of curve order
184
185
Returns:
186
int, converted integer
187
"""
188
189
def bits2octets(data, order):
190
"""
191
Convert bit string to octet string per RFC 6979.
192
193
Parameters:
194
- data: bytes, input bit string
195
- order: int, curve order
196
197
Returns:
198
bytes, converted octet string
199
"""
200
```
201
202
### Low-level ECDSA Operations
203
204
Core elliptic curve digital signature algorithm implementation with basic mathematical operations.
205
206
```python { .api }
207
class Signature:
208
"""ECDSA signature container with (r, s) values."""
209
210
def __init__(self, r, s):
211
"""
212
Create signature from r and s values.
213
214
Parameters:
215
- r: int, r component of signature
216
- s: int, s component of signature
217
"""
218
219
def recover_public_keys(self, hash, generator):
220
"""
221
Recover possible public keys from signature and hash.
222
223
Parameters:
224
- hash: int, hash value that was signed
225
- generator: Point, curve generator point
226
227
Returns:
228
list[Point], possible public key points
229
"""
230
231
class Public_key:
232
"""Low-level ECDSA public key for signature verification."""
233
234
def __init__(self, generator, point, verify=True):
235
"""
236
Create public key from generator and point.
237
238
Parameters:
239
- generator: Point, curve generator
240
- point: Point, public key point
241
- verify: bool, whether to verify point is on curve
242
"""
243
244
def verifies(self, hash, signature):
245
"""
246
Verify signature against hash.
247
248
Parameters:
249
- hash: int, hash value to verify
250
- signature: Signature, signature to verify
251
252
Returns:
253
bool, True if signature is valid
254
"""
255
256
class Private_key:
257
"""Low-level ECDSA private key for signature creation."""
258
259
def __init__(self, public_key, secret_multiplier):
260
"""
261
Create private key from public key and secret.
262
263
Parameters:
264
- public_key: Public_key, corresponding public key
265
- secret_multiplier: int, private key value
266
"""
267
268
def sign(self, hash, k):
269
"""
270
Sign hash with given k value.
271
272
Parameters:
273
- hash: int, hash to sign
274
- k: int, random k value for signature
275
276
Returns:
277
Signature, ECDSA signature
278
279
Raises:
280
RSZeroError: if r or s component is zero
281
"""
282
283
def point_is_valid(generator, x, y):
284
"""
285
Check if point (x, y) is valid on the curve.
286
287
Parameters:
288
- generator: Point, curve generator for curve parameters
289
- x: int, x coordinate
290
- y: int, y coordinate
291
292
Returns:
293
bool, True if point is on curve
294
"""
295
```
296
297
### Utility Functions for Bit Operations
298
299
Low-level utilities for bit manipulation and length calculations.
300
301
```python { .api }
302
def bit_length(x):
303
"""
304
Get bit length of integer.
305
306
Parameters:
307
- x: int, number to measure
308
309
Returns:
310
int, number of bits needed to represent x
311
"""
312
313
def orderlen(order):
314
"""
315
Calculate byte length needed to represent curve order.
316
317
Parameters:
318
- order: int, curve order
319
320
Returns:
321
int, number of bytes needed
322
"""
323
324
def entropy_to_bits(ent_256):
325
"""
326
Convert entropy bytes to bit string.
327
328
Parameters:
329
- ent_256: bytes, entropy data
330
331
Returns:
332
str, bit string representation
333
"""
334
```
335
336
### Exception Classes
337
338
```python { .api }
339
class RSZeroError(RuntimeError):
340
"""Raised when ECDSA signature r or s component is zero."""
341
342
class InvalidPointError(RuntimeError):
343
"""Raised when elliptic curve point is invalid."""
344
345
class JacobiError(Exception):
346
"""Raised when Jacobi symbol computation fails."""
347
348
class SquareRootError(Exception):
349
"""Raised when square root modulo prime fails."""
350
351
class NegativeExponentError(Exception):
352
"""Raised when negative exponent is used inappropriately."""
353
```
354
355
## Usage Examples
356
357
### Deterministic Signature Generation
358
359
```python
360
from ecdsa import SigningKey, NIST256p
361
from ecdsa.rfc6979 import generate_k
362
from ecdsa.numbertheory import square_root_mod_prime
363
import hashlib
364
365
# Generate key and message
366
sk = SigningKey.generate(curve=NIST256p)
367
message = b"Deterministic signature test"
368
digest = hashlib.sha256(message).digest()
369
370
# Generate deterministic k value
371
k = generate_k(
372
order=sk.curve.order,
373
secexp=sk.privkey.secret_multiplier,
374
hash_func=hashlib.sha256,
375
data=digest
376
)
377
378
print(f"Generated k: {k}")
379
print(f"k bit length: {k.bit_length()}")
380
381
# Sign using the deterministic k
382
signature = sk.sign_deterministic(message, hashfunc=hashlib.sha256)
383
print(f"Deterministic signature: {signature.hex()}")
384
385
# Verify the signature is deterministic (same every time)
386
signature2 = sk.sign_deterministic(message, hashfunc=hashlib.sha256)
387
print(f"Signatures match: {signature == signature2}")
388
```
389
390
### Number Theory Operations
391
392
```python
393
from ecdsa.numbertheory import gcd, lcm, jacobi, is_prime, next_prime
394
395
# Greatest common divisor and least common multiple
396
a, b, c = 48, 18, 24
397
print(f"GCD of {a}, {b}, {c}: {gcd(a, b, c)}")
398
print(f"LCM of {a}, {b}: {lcm(a, b)}")
399
400
# Jacobi symbol computation (for quadratic residues)
401
n = 97 # prime
402
for a in [2, 3, 5, 7]:
403
j = jacobi(a, n)
404
print(f"Jacobi({a}/{n}) = {j}")
405
406
# Primality testing
407
candidates = [97, 98, 99, 101]
408
for num in candidates:
409
print(f"{num} is prime: {is_prime(num)}")
410
411
# Find next prime
412
start = 100
413
next_p = next_prime(start)
414
print(f"Next prime after {start}: {next_p}")
415
```
416
417
### Low-level ECDSA Operations
418
419
```python
420
from ecdsa import NIST256p
421
from ecdsa.ecdsa import Private_key, Public_key, Signature
422
from ecdsa.util import randrange
423
import hashlib
424
425
# Create low-level key pair
426
generator = NIST256p.generator
427
secret = randrange(generator.order())
428
public_point = secret * generator
429
public_key = Public_key(generator, public_point)
430
private_key = Private_key(public_key, secret)
431
432
# Sign a hash directly
433
message = b"Low-level signing test"
434
hash_value = int(hashlib.sha256(message).hexdigest(), 16)
435
436
# Generate random k and sign
437
k = randrange(generator.order())
438
signature = private_key.sign(hash_value, k)
439
440
print(f"Signature r: {signature.r}")
441
print(f"Signature s: {signature.s}")
442
443
# Verify signature
444
is_valid = public_key.verifies(hash_value, signature)
445
print(f"Signature valid: {is_valid}")
446
447
# Demonstrate public key recovery
448
possible_keys = signature.recover_public_keys(hash_value, generator)
449
print(f"Recovered {len(possible_keys)} possible public keys")
450
for i, key_point in enumerate(possible_keys):
451
if key_point == public_point:
452
print(f"Original public key found at index {i}")
453
```
454
455
### Working with Elliptic Curve Mathematics
456
457
```python
458
from ecdsa import NIST256p
459
from ecdsa.ellipticcurve import Point
460
from ecdsa.numbertheory import square_root_mod_prime
461
462
# Work with curve points
463
curve = NIST256p.curve
464
generator = NIST256p.generator
465
466
# Generate a random point by scalar multiplication
467
scalar = 12345
468
point = scalar * generator
469
470
print(f"Point coordinates: ({point.x()}, {point.y()})")
471
print(f"Point is on curve: {curve.contains_point(point.x(), point.y())}")
472
473
# Demonstrate point arithmetic
474
point2 = 67890 * generator
475
sum_point = point + point2
476
double_point = 2 * point
477
478
print(f"Point addition works: {sum_point.x()}")
479
print(f"Point doubling works: {double_point.x()}")
480
481
# Work with modular square roots (used in point decompression)
482
p = curve.p()
483
test_value = 12345
484
if jacobi(test_value, p) == 1: # test_value is a quadratic residue
485
sqrt_val = square_root_mod_prime(test_value, p)
486
print(f"sqrt({test_value}) mod {p} = {sqrt_val}")
487
print(f"Verification: {sqrt_val}^2 mod {p} = {(sqrt_val * sqrt_val) % p}")
488
```
489
490
### Polynomial Operations for Advanced Cryptography
491
492
```python
493
from ecdsa.numbertheory import polynomial_reduce_mod, polynomial_multiply_mod
494
495
# Work with polynomials over finite field GF(7)
496
p = 7
497
498
# Define polynomials as coefficient lists (constant term first)
499
poly1 = [1, 2, 3] # 1 + 2x + 3x^2
500
poly2 = [4, 5] # 4 + 5x
501
polymod = [1, 0, 1] # 1 + x^2 (irreducible over GF(7))
502
503
# Multiply polynomials
504
product = polynomial_multiply_mod(poly1, poly2, polymod, p)
505
print(f"Polynomial product: {product}")
506
507
# Reduce polynomial
508
poly_large = [1, 2, 3, 4, 5] # 1 + 2x + 3x^2 + 4x^3 + 5x^4
509
reduced = polynomial_reduce_mod(poly_large, polymod, p)
510
print(f"Reduced polynomial: {reduced}")
511
```