KRYPTOG Logs

Computing $x^e \mod N$ (forward) is easy via SAM, but the inverse operations — e-th root mod N and discrete logarithm mod p — are computationally infeasible without special knowledge. This asymmetry IS asymmetric cryptography. * Both functions are easy forward, hard backward. RS...

Quiz: KRYPTOG / Mathematics for Asymmetric Cryptography | updated: Oct 22, 2026

A cyclic group can be generated entirely by a single element (the generator/primitive element). Diffie-Hellman and ECC rely on cyclic groups. * A generator's successive powers visit every element: 2 sweeps ℤ₉* as 2→4→8→7→5→1 before returning to the start, which is exactly what m...

Quiz: KRYPTOG / Mathematics for Asymmetric Cryptography | updated: Oct 22, 2026

$\mathbb{Z}_p^*$ has order $p - 1$, which is always even (since $p > 2$) and therefore never prime. For maximum security, DH needs a subgroup whose order is a large prime — to prevent small-subgroup attacks. The problem: For DH, we work in $\mathbb{Z}_p^* = \{1, ..., p-1\}$ unde...

Quiz: KRYPTOG / Mathematics for Asymmetric Cryptography | updated: Oct 22, 2026

If $\gcd(a, n) = 1$, reduce the exponent mod $\varphi(n)$ and the base mod $n$. Here $14^{51} \equiv 5^{3} \equiv 8 \pmod 9$. The general rule (Euler, with Fermat as the prime case): for $\gcd(a, n) = 1$, $$a^y \equiv a^z \pmod n \quad\text{whenever}\quad y \equiv z \pmod{\varphi...

Quiz: KRYPTOG / Mathematics for Asymmetric Cryptography | updated: Oct 22, 2026

There are astronomically many primes — about $10^{613}$ primes with exactly 2048 bits, vastly more than atoms in the universe ($10^{80}$). The Gauss pi function estimates: $\pi(x) \approx \frac{x}{\ln(x)}$. * Gauss's π(x) tracks x/ln(x) closely: primes thin out only slowly, so e...

Quiz: KRYPTOG / Mathematics for Asymmetric Cryptography | updated: Oct 22, 2026

$2^{2048}$ has 617 decimal digits — a number vastly larger than the number of atoms in the universe ($10^{80}$). Approximation formulas: $2^{10} = 1024 \approx 10^3$, so $2^{10} \approx 10^3$ Number of digits of $2^x$: $\lfloor x \cdot \log_{10} 2 \rfloor + 1 \approx x \cdot 0.3...

Quiz: KRYPTOG / Mathematics for Asymmetric Cryptography | updated: Oct 22, 2026

False — $3^{-1} \mod N$ exists only when $\gcd(3, N) = 1$. If $N$ is a multiple of 3 (like $N = 9, 15, 21, ...$), the inverse does not exist. When it works: $3^{-1} \mod 7 = 5$ (since $5 \cdot 3 = 15 \equiv 1 \mod 7$) ✓ When it fails: $3^{-1} \mod 9$ → no solution exists (since $...

Quiz: KRYPTOG / Mathematics for Asymmetric Cryptography | updated: Oct 22, 2026

$2^{3072} \approx 10^{925}$, so $N$ has about 925 digits and each prime about 460 digits. There are roughly $10^{397}$ primes with exactly 400 digits. Digits of the primes: use $2^{10} \approx 10^{3}$: $$2^{3072} = (2^{10})^{307.2} \approx (10^{3})^{307.2} = 10^{921.6} \approx 10...

Quiz: KRYPTOG / Mathematics for Asymmetric Cryptography | updated: Oct 22, 2026

The deterministic method constructs primes using formulas (fast but no formula generates ALL primes). The probabilistic method tests random candidates with Miller-Rabin (slower but reliable). * Generating a large prime: pick a random odd candidate, screen it against small primes...

Quiz: KRYPTOG / Mathematics for Asymmetric Cryptography | updated: Oct 22, 2026

Division mod N is multiplication by the inverse: $\frac{x}{y} \mod N \equiv (x \cdot y^{-1}) \mod N$. You NEVER actually divide — you find the inverse and multiply. Formula: $z \equiv \frac{x}{y} \mod N \equiv (x \cdot y^{-1}) \mod N$ Verification: $x \equiv (z \cdot y) \mod N$ E...

Quiz: KRYPTOG / Mathematics for Asymmetric Cryptography | updated: Oct 22, 2026