Helper method to create a private key from p, q, e, n values Args: p: prime factor p q: prime factor q e:

Parse input (hex or numerical)

Finds item index in O(log2(N))

Helper method to create a private key from publickey with p and q Args: publickey: PublicKey object with n, e, p, q attributes

Build QS factor base: -1 + primes (from first B primes). Every prime p <= the B-th prime is included. Sieving roots: - p = 2 →

Generate keypair from p, q, e, n

Legendre symbol (a/p) for odd prime p. Returns 0 if p|a, 1 if a is a quadratic residue mod p, p-1 (≡ -1) if QNR. Uses Euler's criterion: a^((p

Gaussian elimination over GF(2) with pivot tracking. Each element of *rows* is (bitmask, relation_mask). Returns the transformed list in red

Decrypt data with private key :param cipher: input cipher :type cipher: string

Dixon's smooth-number factorisation (Dixon, Math. Comp. 36, 1981). Collects relations a_i² ≡ ∏ pⱼ^{e_{ij}} (mod n) that are B-smooth, solves a

Quadratic Sieve factorisation. Complexity: L[1/2, 1] = exp(sqrt(log n log log n)). Sieves Q(x) = x^2 - n for B-smooth values, then reuses th

Compute sum of digits efficiently without string conversion.

Return attack name

" Taken from https://gist.github.com/Ayrx/5884790 Implementation uses the Miller-Rabin Primality Test The optimal number of rounds for th

String to number.

Sieve Q(x) = x^2 - n over x in [sqrt(n)-M, sqrt(n)+M]. Returns list of (x, parity_mask, full_exp) relations compatible with _try_smooth_depen

Rational_to_contfrac implementation

Run attacks on single keys

Pollard rho with brent optimizations taken from: https://gist.github.com/ssanin82/18582bf4a1849dfb8afd

Contfrac_to_rational implementation

Parse input (hex or numerical)

greatest integer l such that b**l < = x.

Number to string.

Euler totient φ(n). Computed from the prime factorisation of n via: φ(n) = n ∏_{p|n} (1 − 1/p). The `factors` argument must contain ever

Prime-base square-collision factoring. Iterates i from ⌊√n⌋ upward computing i² mod n. When i² ≡ p² (mod n) for the current prime p, returns

Find a factor of N using the strong pseudoprime (Miller-Rabin) test. Iterates prime bases a, climbs the ladder a^f, a^{2f}, a^{4f}, ..., a^{N-1},

Code borrowed and adapted from the wikipedia: https://en.wikipedia.org/wiki/Shanks%27s_square_forms_factorization It may contain bugs

Fermat's prime criterion Returns False if n is definitely composite, True if possible prime.

Try each null-space vector for a nontrivial split x² ≡ y² (mod n). Returns (p, q) on success, None if every dependency gives x ≡ ±y.

Test if everything is ok for running attack

Return p and q from (n, p) or (n, q)

Dynamic load attacks according to context (single key or multiple keys)

Calculates a^{b} mod n when b is negative

Basic pre Attack checks implementation

Print results to output

Code taken and heavy modified from https://github.com/google/paranoid_crypto/blob/main/paranoid_crypto/lib/rsa_util.py Licensed under open so

Collect B-smooth relations a² ≡ ∏ pⱼ^{eⱼ} (mod n). Returns (relations, split) where *split* is (p, q) if an immediate factor was found (a² ≡

Return (n, PrivateKey) for the given p, q, e.

Use sage's internal quadratic sieve method. If input is less than 40 digits, i'll fallback to sage factor method.

Return a boolean if requested actions are done avoiding running extra attacks

e1 --> Public Key exponent used to encrypt message m and get ciphertext c1 e2 --> Public Key exponent used to encrypt message m and get ciphe

Convergents_from_contfrac implementation

Euler's factorisation method. Finds two distinct representations of n as a sum of two squares, then recovers factors via GCD of the mixed sums

based on: https://github.com/hirogwa/crypto-playground/blob/master/break_rsa.py premise: P is prime > 2 and sqrt(2PN) is close to (Pp + 2q)/2

Factor n of the form x^y · x^z = x^{y+z} where x is prime. Uses integer root extraction: for each exponent k ≥ 2, compute the k-th root r = fl

Return a boolean value according to requested actions (private, decrypt) if actions are done or not

Hart's one line attack taken from wagstaff the joy of factoring

its orders of magnitude faster than invert(a, 2^k) code borrowed from: https://algassert.com/post/1709

True if n is a Lucas number (A000032).

based on: https://programmingpraxis.com/2017/08/22/lehmans-factoring-algorithm/

fermat based integer factorization

Helper function for williams_pp1(). Multiplies along a Lucas sequence modulo n.

Pollard P1 implementation

https://math.stackexchange.com/questions/185524/pollard-strassen-algorithm

Print extra output according to requested action. Decrypt data if needed.

Tonelli-Shanks modular squareroot algorithm

Computes an approximation to the modular inverse square root of `n` with `k` bits.

fibonacci sequence nth item modulo p