CryptoUtils

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

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.

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.

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).