Functions

CryptoUtils

Number to bytes conversion

``b2n(str::String) -> BigInt``

Converts a byte-string to a number, converting the string from base 256 to base 10.

``````julia> b2n("Hello world!")
22405534230753963835153736737``````
``n2b(n::Integer) -> String``

Converts a number to its bytes representation, effectively writing the number in base 256, and returning the corresponding bytes.

``````julia> n2b(22405534230753963835153736737)
"Hello world!"``````

Prime numbers

``random_prime(bitsize::Integer) -> BigInt``

Return a random prime with `bitsize` bits.

``````julia> random_prime(42)
2458636110727``````
``safe_prime(bitsize::Integer) -> BigInt``

Return a random safe-prime `q` of the form `q = 2 * p + 1` where `p` is also a prime number. The returning prime number has `bitsize` bits.

``````julia> safe_prime(10)
1439``````
``tower_two_prime(bitsize::Integer, tower_len::Integer) -> BigInt``

Return a random prime of the form `2^towerlen * q + 1` with `bitsize` bits and where `q` is also a prime.

``````julia> tower_two_prime(22, 6)
2362433``````
``get_first_primes(k::Integer) -> Collection``

Output the first `k` prime numbers.

``````julia> get_first_primes(10)
10-element Array{Int64,1}:
2
3
5
7
11
13
17
19
23
29``````
``twin_primes(bitsize::Integer)``

Return a pair of prime numbers `p, p + 2` with `bitsize` bits.

This might take a while to run.

Number theory

``find_quadratic_non_residue(p::Integer)``

Return a random number `R` which has no square root mod `p`, i.e., `x^2 == R mod p` has no solutions.

``is_quadratic_residue(a::Integer, p::Integer) -> Bool``

Return true or false depending on wheter `a` is a quadratic residue mod `p`.

That is, it checks if `x^2 == a mod p` has solutions.

``sqrt_mod_prime(a::Integer, p::Integer) -> Integer``

Solves `x^2 == a mod p` and returns one of the square roots `r`. The other root is `p - r`. If there are no solutions, throws an exception.

``````julia> sqrt_mod_prime(33^2, 73)
33``````
``jacobi(n::Integer, k::Integer)``

Return the Jacobi symbol of `n, k`.

`k` should be an odd number.

``legendre(a::Integer, p::Integer)``

Return the Legendre symbol of `(a, p)`.

`p` should be an odd prime number.

``continued_fraction(a::T, b::T) where T <: Integer``

Return the continued fraction of the rational `a/b`.

Example

``````julia> continued_fraction(31, 73)
6-element Array{Int64,1}:
0
2
2
1
4
2``````
``convergents(a::T, b::T) where T <: Integer``

Return the convergents of a rational `a/b`.

Example

``````julia> convergents(31, 73)
6-element Array{Rational,1}:
0//1
1//2
2//5
3//7
14//33
31//73``````
``convergents(cont_fraction::Array)``

Return the convergents given the continued fraction of a rational.

``surd(n::BigInt, k::Int64)``

Return largest integer smaller or equal than the `k`-th root of `n`.

``hoc_sqrt(a::Integer, p::Integer)``

Algorithm from Handbook of cryptography, Koblitz pp 48-49. Finds a solution to `x^2 == a mod p`.

It assumes such solution exists.

Running time highly depends on |alpha|, assuming `p-1 = 2^alpha * s`, for an odd `s`.

``tonelli_shanks(a::Integer, p::Integer)``

Implements the Tonelli Shanks algorithm for computing square roots modulo a prime number.

It assumes such square roots exist.

``is_generator(g::Integer, q::Integer, factors::Array) -> Bool``

Returns true if `g` is a generator of `Z_q` where `q` is prime and `factors` is the prime factorization of `q - 1 = p1^e1 * p2^e2 ... * pk^ek`.

``````q = 2^7 * 5 + 1
is_generator(2, q, [2, 5]) -> false
is_generator(3, q, [2, 5]) -> true``````
``get_safe_prime_generator(q::BigInt) -> BigInt``

Returns a generator of `Z_q`, where `q = 2 * p + 1` with `q, p` primes.

Cryptography

``factor_with_ed(n::Integer, e::Integer, d::Integer) -> (Integer, Integer)``

Factors `n = p*q` given `(e, d)` such that `e*d = 1 mod phi(n)` Stinson page 204 - algorithm 5.10

``wiener(n::Integer, e::Integer, dujella_bound=20)``

Factors the semiprime `n`, assuming Wiener's attack holds: `d < n^(1/4)`, where `d*e = 1 mod phi(n)`.

Uses Dujella extension attack. Increasing the `dujella_bound` argument slows the running time but increases chances of finding the correct `d` in case `d ~ n^(1/4)`.