Crypto – Gaussian-Integer RSA

An RSA analog over Zi, using two inert Gaussian primes (rational primes \(p \equiv 3 \pmod 4\)) in place of RSA’s two rational primes. Each block carries two independent components (real and imaginary), so throughput roughly doubles versus plain RSA at the same key size. See the module docstring below for the underlying math.

Warning

Teaching implementation only – no OAEP-style padding, not side-channel hardened. Do not use to protect real secrets.

from gint.crypto import generate_keypair, encrypt_text, decrypt_text

public_key, private_key = generate_keypair(bits=512)
ciphertext = encrypt_text("Gaussian primes are neat.", public_key)
decrypt_text(ciphertext, private_key)   # 'Gaussian primes are neat.'

Gaussian-integer RSA: an RSA analog over the ring of Gaussian integers Z[i].

Classic RSA works in Z/(n) for n = p*q, a product of two rational primes, using Euler’s theorem: m**phi(n) == 1 (mod n) for m coprime to n, where phi(n) = (p-1)*(q-1).

This module runs the identical construction one level up, in Z[i]/(n) for n = p*q, a product of two inert rational primes (primes p with p % 4 == 3, which stay prime – do not factor further – in Z[i]). For such a prime p, Z[i]/(p) is a finite field of p**2 elements (isomorphic to GF(p**2)), so its multiplicative group has order p**2 - 1, giving the field-theoretic analog of Fermat’s little theorem: m**(p**2) == m (mod p) for every Gaussian integer m, exactly as m**p == m (mod p) holds for ordinary integers. Combining the two primes via the Chinese Remainder Theorem gives

phi(n) = (p**2 - 1) * (q**2 - 1)

and the same RSA identity m**(e*d) == m (mod n) whenever e*d == 1 (mod phi(n)), for every Gaussian integer m – not just ones coprime to n, by the usual per-prime argument.

Because a Gaussian integer carries two independent components (real and imaginary), each block encrypted this way carries twice the payload of a plain-RSA block for a modulus of the same size, at the same modular- exponentiation cost per block.

This module is a self-contained teaching implementation of that analog, built on gint.zi.Zi. It is NOT a vetted, side-channel-resistant, or otherwise production-ready cryptographic implementation – as with textbook RSA, it has no OAEP-style padding scheme, so it should not be used to protect real secrets.

Example: >>> from gint.crypto import generate_keypair, encrypt_text, decrypt_text >>> public_key, private_key = generate_keypair(bits=256) >>> ciphertext = encrypt_text(“Gaussian primes are neat.”, public_key) >>> decrypt_text(ciphertext, private_key) ‘Gaussian primes are neat.’

class gint.crypto.GaussianRSAPublicKey(n: int, e: int)

Bases: NamedTuple

A public key: modulus n and public exponent e.

n = p * q is an ordinary (rational) integer – the product of two distinct inert Gaussian primes – but all encryption arithmetic is carried out in Z[i]/(n).

n: int

Alias for field number 0

e: int

Alias for field number 1

class gint.crypto.GaussianRSAPrivateKey(n: int, d: int, p: int, q: int)

Bases: NamedTuple

A private key: modulus n, private exponent d, and the two inert primes p, q whose product is n (kept for reference; this implementation does not use the CRT speedup during decryption).

n: int

Alias for field number 0

d: int

Alias for field number 1

p: int

Alias for field number 2

q: int

Alias for field number 3

class gint.crypto.GaussianRSACiphertext(blocks: List[Zi], length: int)

Bases: NamedTuple

The result of encrypting a byte string: a list of encrypted Zi blocks, plus the original (unpadded) byte length needed to strip padding on decryption.

blocks: List[Zi]

Alias for field number 0

length: int

Alias for field number 1

gint.crypto.generate_keypair(bits: int = 256, e: int = 65537)

Generate a Gaussian-RSA keypair.

Picks two distinct random inert Gaussian primes p, q (each a bits-bit rational prime with p % 4 == 3), sets n = p*q, and derives a private exponent d = e^-1 (mod phi(n)) with phi(n) = (p**2 - 1) * (q**2 - 1). If the requested e is not coprime with phi(n) for a given (p, q) pair, q is resampled until it is.

Parameters:

• bits – bit length of each of the two primes p, q. The modulus n is therefore about 2 * bits bits, but (per the module docstring) each block carries two components, each reduced mod n, so throughput is comparable to plain RSA with an n of about twice that size.

• e – public exponent. Defaults to 65537, the conventional RSA choice.

Returns:

a (public_key, private_key) pair.

gint.crypto.encrypt_block(m: Zi, public_key: GaussianRSAPublicKey) → Zi

Encrypt a single message block. m must be a Zi with both components in [0, public_key.n) – the canonical representatives of Z[i]/(n) that this module’s byte-level encoding produces.

gint.crypto.decrypt_block(c: Zi, private_key: GaussianRSAPrivateKey) → Zi

Decrypt a single ciphertext block, returning the original Zi message block with both components in [0, private_key.n).

gint.crypto.block_capacity(n: int) → int

Number of bytes safely packed into each of a Zi block’s two components for modulus n, leaving a one-bit safety margin so the resulting integer is always strictly less than n.

gint.crypto.encrypt_bytes(data: bytes, public_key: GaussianRSAPublicKey) → GaussianRSACiphertext

Encrypt an arbitrary byte string as a sequence of Zi blocks. Each block packs 2 * block_capacity(n) bytes: the first half becomes the real component, the second half the imaginary component. The final block is zero-padded; the original length is carried in the returned GaussianRSACiphertext so decryption can strip it.

gint.crypto.decrypt_bytes(ciphertext: GaussianRSACiphertext, private_key: GaussianRSAPrivateKey) → bytes

Inverse of encrypt_bytes().

Raises:

ValueError – if a decrypted block doesn’t fit back into block_capacity(private_key.n) bytes per component. With the matching private key this never happens (see block_capacity’s one-bit safety margin); it signals a key/ciphertext mismatch, e.g. decrypting with the wrong private key.

gint.crypto.encrypt_text(text: str, public_key: GaussianRSAPublicKey, encoding: str = 'utf-8') → GaussianRSACiphertext

Encrypt a string (UTF-8 by default). Convenience wrapper around encrypt_bytes().

gint.crypto.decrypt_text(ciphertext: GaussianRSACiphertext, private_key: GaussianRSAPrivateKey, encoding: str = 'utf-8') → str

Inverse of encrypt_text().

Further Reading

Foundational paper

• Elkamchouchi, H., Elshenawy, K., Shaban, H. (2002). Extended RSA Cryptosystem and Digital Signature Schemes in the Domain of Gaussian Integers. Proceedings of the 8th International Conference on Communication Systems (ICCS 2002), Vol. 1, pp. 91-95, IEEE. The paper that introduced this scheme: modulus N = P*Q for Gaussian primes P, Q with |P|=p, |Q|=q ordinary primes, key equation ed = 1 (mod (p^2-1)(q^2-1)). IEEE Xplore – Semantic Scholar

Extensions and variants

• El-Kassar, A.N., Haraty, R., Awad, Y., Debnath, N.C. (2005). Modified RSA in the Domains of Gaussian Integers and Polynomials over Finite Fields. CAINE 2005, pp. 298-303. Free PDF

• Pradhan, S., Sharma, B.K. (2014). A Modified Variant of RSA Algorithm for Gaussian Integers. In SocProS 2012, Advances in Intelligent Systems and Computing, Springer. SpringerLink

• Cotan, P., Teseleanu, G. generalized the key equation to ed - k(p^n-1)(q^n-1) = 1 over Galois fields of order n >= 1 (n=2 recovers the Gaussian-integer case); see the partial-exposure-attacks paper below.

Cryptanalysis

Worth reading precisely because this module is a teaching implementation: the scheme has been broken under the same conditions plain RSA is (small or exposed private exponent), via continued-fraction and lattice methods analogous to Wiener’s attack on RSA.

• Nitaj, A., et al. Cryptanalysis of RSA-type Cryptosystems Based on Lucas Sequences, Gaussian Integers and Elliptic Curves. Free PDF (HAL) – ScienceDirect

• Bunder, M., Nitaj, A., Susilo, W., Tonien, J. (2016). A New Attack on Three Variants of the RSA Cryptosystem. ACISP 2016, LNCS 9723, pp. 258-268, Springer. SpringerLink

• Peng, L., Hu, L., Lu, Y., Wei, H. (2016). An Improved Analysis on Three Variants of the RSA Cryptosystem. Inscrypt 2016, LNCS 10143, Springer.

• More recent lattice and partial-exposure attacks on the generalized Cotan-Teseleanu family: Partial Exposure Attacks (2025, open access) – A Lattice Attack – Further Cryptanalysis – Further cryptanalysis of some variants

Survey / background

• Koval, A. (dissertation, NJIT). Security Systems Based on Gaussian Integers. Covers the extended RSA, ElGamal, and an extended Rabin cryptosystem over Z[i], with a caveat worth echoing here: the extension only helps if breaking plain RSA turns out to be strictly easier than factoring, and even then it is not guaranteed to add security. Free PDF