Modular arithmetic
All arithmetic happens in ℤ_q, the integers modulo a prime. Results wrap around, so every value stays between 0 and q − 1.
mod qBigInteger
CS285 · Discrete Mathematics
Talk in public. Share a secret. mod q.
A Java implementation of the Diffie–Hellman key exchange. Two parties each keep a private exponent and publish αX mod q. From what they receive, both compute the same key K, then use it to encrypt and decrypt a message. Recovering a private exponent from the public values is the discrete logarithm problem.
K = 2
ord23(5) = 22
7
Java classes, one per responsibility
3
Run modes: fixed example, auto-generated, live
22/ 22
Nonzero residues mod 23 generated by α = 5
256bit
SHA-256 keystream derived from the shared key
§ 00 · Abstract
The security rests on a function that is easy to compute and hard to invert.
The project shows how two participants can establish a shared secret using public-key cryptography. It implements the Diffie–Hellman key exchange, so a key can be agreed over an insecure channel without either private value ever being sent.
The derived key then drives message encryption and decryption. The program validates every input and offers two ways to explore it: a guided numerical example and an interactive live mode.
Computing αx mod q is fast. Going the other way, recovering x from the result, is the discrete logarithm problem, which is infeasible in practice when q is large.
§ 01 · The protocol
Everything in the middle column is public. The key never is.
The worked example from the report, with q = 23 and α = 5. Eve sees every value that crosses the channel. To learn K she would have to solve 5x ≡ 8 (mod 23) for x.
ACar 1 · Alicekeeps Xa secret
Public channelEve reads everything here
BCar 2 · Bobkeeps Xb secret
1 · Parameters
Accepts the shared prime and base.
agreed in the open
q = 23, α = 5
A prime and a primitive root, with 1 < α < q.
1 · Parameters
Accepts the shared prime and base.
2 · Private key
Xa = 6
never leaves Alicenothing sent
Each side picks 1 ≤ X ≤ q − 2 on its own.
2 · Private key
Xb = 15
never leaves Bob3 · Public key
Ya = 56 mod 23 = 8
exchanged
Ya = 8→
←Yb = 19
3 · Public key
Yb = 515 mod 23 = 19
4 · Shared key
K = 196 mod 23 = 2
Eve's problem
5x ≡ 8 (mod 23)
Knowing q, α, Ya, Yb is not enough without a discrete logarithm.
4 · Shared key
K = 815 mod 23 = 2
5 · Encrypt
XOR the message with SHA-256(K), then Base64-encode it.
ciphertextia7NqGzfh+I5LTLc5lVhclaXOtXeTEEk…
5 · Decrypt
The same keystream undoes the XOR: Decryption OK = true
§ 02 · Key exchange lab
Pick a prime, a base and two secrets. Watch the keys agree.
The same computation as Main.runLiveMode(), in your
browser. The ring shows the subgroup ⟨α⟩: if
α is a primitive root, its powers reach every
nonzero residue. If it isn't, most of the ring stays dark.
KeyExchange · modPow(α, X, q)
AliceBobshared K
- Ya = αXa
- 8
- Yb = αXb
- 19
- Alice's K
- 2
- Bob's K
- 2
- ordq(α)
- 22
- Possible keys
- 22
- Eve's brute force
- 6tries
Validator: 1 < α < q
Helpers: 1 ≤ X ≤ q − 2
§ 03 · The discrete maths
Six ideas from the course, each one doing a job in the code.
Every concept below maps to a specific line of the Java implementation.
Primes and primality
The modulus must be prime so that every nonzero residue has an inverse. Validator runs a probabilistic primality test with certainty 100.
Validator.isPrimeisProbablePrime(100)Primitive roots
A primitive root α generates the whole multiplicative group: its powers hit all q − 1 nonzero residues before repeating.
Parameters.getAlphaord(α) = q − 1Fast exponentiation
Square-and-multiply computes α^X mod q in about log₂ X steps, which makes public keys cheap to compute even for huge exponents.
modPowKeyExchangeDiscrete logarithm
Given α, q and Y = α^X mod q, finding X has no known efficient method for well-chosen large primes. This is the hard problem the protocol relies on.
Eve's problemXOR and hashing
The shared key is hashed with SHA-256 into 32 bytes and XORed with the message. Because (m ⊕ k) ⊕ k = m, the same operation decrypts.
Encryptor.xorSHA-256§ 04 · Architecture as a graph
Seven classes, five dependencies.
Read the codebase as a directed graph: each vertex is a class and an
edge u → v means u
uses v. Main is the entry point:
it runs the menu and calls modPow itself.
KeyExchange packages the same computation as a reusable
subclass of Parameters, and Utils is an
isolated vertex that the main flow never calls. Select a vertex to
read its source.
G = (V, E) · class dependencies
usesextends
- Vertices
- |V| = 7
- Edges
- |E| = 5
- Isolated
- Utils
§ 05 · Evidence
Every run ends the same way: the keys match.
Console output from the three test scenarios in the report. Select a screenshot to enlarge it.
§ 06 · The team
Four people, seven classes.
Each member owned part of the code and part of the write-up. Select a member to see what they did.
§ 07 · Explore
From the first definition to the final report.
About
Scope, purpose and how the implementation connects theory with working software.
OpenIntroduction
The Diffie–Hellman model, its security assumption and a verified numerical example.
OpenArchitecture
Class responsibilities, the five-stage workflow and the two operating modes.
OpenResults
Live mode, input validation and the fixed numerical example, with screenshots.
OpenAdvantages & limitations
Why plain DH needs authentication, and how it compares with ECDH.
OpenConclusion
What was achieved, what was learned and what comes next.
OpenReferences
Diffie & Hellman (1976) and the other sources behind the project.
OpenReport
The final submitted report, embedded and downloadable.
OpenCS285 · Discrete Mathematics for Computing
Read the full report, or run the code yourself.
The report covers the mathematics, the design and every test case. The repository has the complete Java source.