Educational Cryptography Suite

Intuition, Vocabulary and Foundations

Cryptographic number theory uses easy forward operations whose inverses appear difficult at approved scales. Multiplying primes is easy while factoring their product may be hard; computing $(g^a\bmod p)$ is easy while recovering $(a)$ may be hard in a suitable group. Elliptic curves replace integer multiplication with repeated point addition.

A toy RSA example uses $(p=61)$, $(q=53)$, $(n=3233)$, $(e=17)$, and $(d=2753)$. Message $(65)$ encrypts to $(2790)$ and decrypts correctly, but the modulus is trivially factorable and textbook RSA is deterministic. Diffie–Hellman similarly demonstrates a shared $(g^{ab})$, Rabin demonstrates four square roots, and elliptic curves demonstrate scalar multiplication. None of these bare mechanisms is a secure protocol.

Toy cryptography can demonstrate algebra and failure modes, but cannot establish production security. Real security also requires a threat model, approved parameters, secure randomness, validation, authenticated protocols, side-channel defenses, and audited libraries.

Concept	Transparent example	Unsafe boundary	Question answered
RSA	$(c=m^e\bmod n)$	Tiny modulus or textbook encryption	Does the exponent relation round-trip?
Diffie–Hellman	Both parties derive $(g^{ab})$	Tiny group, reused secret, unchecked peer	Is discrete logarithm hard in the validated group?
Rabin	$(c=m^2\bmod pq)$	Assuming decryption has one root	Which of four roots matches the encoding?
Elliptic curve	$(Q=kP)$ on a nonsingular curve	Accepting off-curve or wrong-subgroup points	Is the point valid in the intended subgroup?
Key material	Uniform secret in the allowed interval	Timestamp or ordinary PRNG output	Is the secret unpredictable and unbiased?
Security parameter	Approved curve, modulus, and hash	Ad hoc large-looking numbers	What attack cost and lifetime are targeted?
Toy attack	Factor $(3233)$ by trial division	Extrapolating toy work to modern keys	Why do deliberately small parameters fail?
Threat model	Active modification and replay included	Testing confidentiality only	Which attacker capabilities are addressed?

Step-by-Step Derivations and Algorithms

RSA chooses $(n=pq)$, $(e)$ coprime to $(lambda(n))$, and $(d=e^{-1}\bmod\lambda(n))$. Modular exponentiation costs logarithmically many multiplications. Factoring a tiny $(n)$ recovers the private exponent; bounded trial division costs $(O(\sqrt n))$.

Diffie–Hellman publishes $(A=g^a)$ and $(B=g^b)$, then both sides derive $(g^{ab})$. Exhaustive exponent search breaks only the deliberately tiny example. Rabin squares modulo $(pq)$; roots modulo $(p)$ and $(q)$ combine with CRT into four candidates. On $(y^2=x^3+ax+b\pmod p)$, double-and-add computes $(kP)$ in $(O(\log k))$ point operations after curve and point validation.

Educational Cryptography Suite algorithm map

flowchart TD
    A[Choose primitive and threat model] --> B[Validate toy parameters]
    B --> C{Educational workflow}
    C -->|RSA| D[Round-trip then factor tiny modulus]
    C -->|Diffie Hellman| E[Exchange then enumerate tiny exponent]
    C -->|Rabin| F[Square then show four roots]
    C -->|Elliptic curve| G[Validate then multiply point]
    D --> H[Report assumptions and failures]
    E --> H
    F --> H
    G --> H

Each demo preserves its defining algebraic relation and rejects values outside its domain. Forward operations are logarithmic in exponent bits; the bounded toy attacks intentionally use $(O(\sqrt n))$ division or $(O(r))$ enumeration and must remain confined to unsafe teaching parameters.

Implementation, Complexity and Engineering

The code is explicitly TOY_ONLY. It uses fixed tiny parameters and omits standardized padding, authenticated encryption, constant-time execution, secure storage, protocol negotiation, and hardened parsing. Production applications must use maintained high-level cryptographic APIs and operating-system-backed cryptographic randomness.

from math import gcd, isqrt, lcm

TOY_ONLY = True


def egcd(a, b):
    old_r, r, old_s, s = a, b, 1, 0
    while r:
        q = old_r // r
        old_r, r, old_s, s = r, old_r - q * r, s, old_s - q * s
    return old_r, old_s


def inverse(value, modulus):
    divisor, coefficient = egcd(value % modulus, modulus)
    if divisor != 1:
        raise ValueError("inverse does not exist")
    return coefficient % modulus


def rsa_keys(p, q, e):
    if p == q or p < 3 or q < 3:
        raise ValueError("distinct odd toy primes required")
    modulus = p * q
    lam = lcm(p - 1, q - 1)
    if gcd(e, lam) != 1:
        raise ValueError("invalid public exponent")
    return (modulus, e), (modulus, inverse(e, lam))


def rsa_apply(value, key):
    modulus, exponent = key
    if not 0 <= value < modulus:
        raise ValueError("representative outside modulus")
    return pow(value, exponent, modulus)


def factor_toy(modulus, limit=100000):
    if limit < 1:
        raise ValueError("positive work limit required")
    for trials, candidate in enumerate(range(2, isqrt(modulus) + 1), 1):
        if trials > limit:
            return None
        if modulus % candidate == 0:
            return candidate, modulus // candidate
    return None


def dh_public(generator, secret, prime):
    if not 2 <= generator <= prime - 2 or not 1 <= secret <= prime - 2:
        raise ValueError("invalid toy DH input")
    return pow(generator, secret, prime)


def discrete_log_toy(generator, target, prime, bound):
    if not 0 <= bound <= 100000:
        raise ValueError("educational search must be bounded")
    value = 1
    for exponent in range(bound + 1):
        if value == target:
            return exponent
        value = value * generator % prime
    return None


def crt(a, p, b, q):
    return (a + p * ((b - a) * inverse(p, q) % q)) % (p * q)


def rabin_roots(ciphertext, p, q):
    if p == q or p % 4 != 3 or q % 4 != 3:
        raise ValueError("distinct Blum primes required")
    modulus = p * q
    rp = pow(ciphertext, (p + 1) // 4, p)
    rq = pow(ciphertext, (q + 1) // 4, q)
    return tuple(sorted({crt(sp * rp % p, p, sq * rq % q, q)
                         for sp in (1, -1) for sq in (1, -1)}))


def on_curve(point, prime, a, b):
    if point is None:
        return True
    x, y = point
    return 0 <= x < prime and 0 <= y < prime and (y*y - x*x*x - a*x - b) % prime == 0


def point_add(left, right, prime, a, b):
    if (4*a*a*a + 27*b*b) % prime == 0:
        raise ValueError("singular curve")
    if not on_curve(left, prime, a, b) or not on_curve(right, prime, a, b):
        raise ValueError("off-curve point")
    if left is None:
        return right
    if right is None:
        return left
    x1, y1 = left
    x2, y2 = right
    if x1 == x2 and (y1 + y2) % prime == 0:
        return None
    slope = ((3*x1*x1 + a) * inverse(2*y1, prime) if left == right
             else (y2-y1) * inverse(x2-x1, prime)) % prime
    x3 = (slope*slope - x1 - x2) % prime
    return x3, (slope*(x1-x3) - y1) % prime


def scalar_multiply(scalar, point, prime, a, b):
    if scalar < 0 or not on_curve(point, prime, a, b):
        raise ValueError("invalid scalar or point")
    result = None
    while scalar:
        if scalar & 1:
            result = point_add(result, point, prime, a, b)
        point = point_add(point, point, prime, a, b)
        scalar >>= 1
    return result


public, private = rsa_keys(61, 53, 17)
ciphertext = rsa_apply(65, public)
assert ciphertext == 2790 and rsa_apply(ciphertext, private) == 65
assert factor_toy(3233) == (53, 61)

p, g, alice, bob = 23, 5, 6, 15
A, B = dh_public(g, alice, p), dh_public(g, bob, p)
assert pow(B, alice, p) == pow(A, bob, p)
assert discrete_log_toy(g, A, p, 22) == alice

roots = rabin_roots(20 * 20 % 77, 7, 11)
assert len(roots) == 4 and 20 in roots
assert scalar_multiply(2, (5, 1), 17, 2, 2) == (6, 3)

for invalid in (lambda: rsa_keys(61, 61, 17),
                lambda: rsa_apply(4000, public),
                lambda: discrete_log_toy(5, 8, 23, 100001),
                lambda: point_add((1, 1), (5, 1), 17, 2, 2)):
    try:
        invalid()
        raise AssertionError("invalid input accepted")
    except ValueError:
        pass

print("EDUCATIONAL - NOT FOR PRODUCTION:", public, ciphertext, roots)
print("all tests passed")

Educational choice	Observation	Production failure	Production direction
Tiny RSA modulus	Easy to factor	Private key recovered immediately	Approved sizes, padding, audited API
Textbook RSA	Shows exponent relation	Deterministic and malleable	Standard OAEP or PSS APIs
Small DH group	Attack can be enumerated	Cheap logs and subgroup attacks	Approved groups, validation, KDF, authentication
Fixed secrets	Reproducible trace	Predictable keys	Cryptographic RNG with unbiased sampling
Rabin roots	Shows ambiguity	Wrong root selection	Reviewed encoding or standardized construction
Affine curve formulas	Readable addition	Timing leakage and exceptional cases	Hardened constant-time library formulas
On-curve check	Rejects malformed coordinates	Wrong subgroup may remain	Subgroup validation or safe encodings
Round-trip tests	Find functional bugs	Do not prove security	Test vectors, fuzzing, review, and audit

Applications, Case Studies and Exercises

An approachable suite prints parameters, intermediate identities, successful round trips, and attacks enabled by intentionally unsafe sizes. A professional case study should instead produce an architecture decision record covering threats, approved protocols, key lifetimes, randomness, validation, library selection, updates, and incident response. Every toy primitive must be replaced before deployment.

Deliverable

Apply Educational Cryptography Suite

Case study 1 — break the toys. Run RSA with $(61)$, $(53)$, exponent $(17)$, and message $(65)$; confirm ciphertext $(2790)$, factor $(3233)$, reconstruct the private key, and decrypt. Enumerate the exponent in the $(p=23,g=5)$ DH example. Record work counts and explain why these parameters are intentionally unsafe.

Case study 2 — production migration. Review a prototype using textbook RSA, fixed DH secrets, and custom curve arithmetic. Cover passive observation, modification, replay, key theft, invalid inputs, and timing. For every toy component, name the missing protection and the audited high-level replacement.

Deliverable. Provide rsa-demo, dh-demo, rabin-demo, curve-demo, and bounded attack-toy commands. Every output begins with EDUCATIONAL - NOT FOR PRODUCTION, rejects malformed values, and lists assumptions and failures. Success requires reproducible tests without any custom primitive on a proposed production path.

Use the suite to understand algebra, validation, and attacks—not to protect data. Define the threat model, use standardized protocols and approved parameters, obtain secrets from a cryptographic RNG, validate inputs, avoid custom encodings and arithmetic, and depend on maintained audited libraries.

Cookie Consent