Math E-122: Algebra & Cryptography

Juspreet Singh Sandhu

May-13, 2018

Abstract

Cryptography is a topic that has fascinated humanity for time immemorial.

From the Atbash

cipher in ancient times to the Enigma

machine in World-

War I/II, Cryptography has been a central tool in intelligence gathering, secret

sharing, and more generally, in Information Privacy. In the modern day and age,

in addition to having numerous such applications, Cryptography is a rich ﬁeld of

intellectual inquiry with deep connections to Abstract Algebra, Computational

Complexity Theory, Number Theory and Lattice Theory. This survey begins

with a brief (but formal) introduction to Ciphers, followed by an introduction

to Symmetric & Asymmetric Key Cryptography. We then give a detailed expo-

sition of the El-Gamal & RSA protocols, and conclude with formal proofs for

the security guarantees of each system by analyzing the computational hardness

of the underlying problems (Discrete-Log, Inverse Modular Exponentiation) us-

ing traditional results from Group Theory (Euler’s Theorem, Fermat’s Little

Theorem).

1 Ciphers, Symmetric & Asymmetric Key Cryp-

tography

We begin by deﬁning a Cipher:

Def

: A Cipher is a 2-tuple E = (E, D) where:

• E : K × M → C is an eﬃcient Encryption Algorithm.

• D : K × C → M is an eﬃcient Decryption Algorithm.

• D(E(k, m)) = m, ∀k ∈ K and ∀m ∈ M.

K denotes the key-space, the set from which a key is chosen. M denotes the

message-space, the set from which a message is chosen. Finally, C denotes the

cipher-space, the set into which messages are encrypted.

In the early days of Cryptography, most Encryption and Decryption protocols

relied on shared secrets in the form of (secret) keys. This meant that prior to

encrypted communication, both parties needed to agree on the same key. This

lead to the development of Symmetric Key Cryptography, with many protocols

implementing the idea of symmetric key generation. An example of such a pro-

tocol is the famous One-Time Pad

Def

: The One-Time Pad is deﬁned by symmetric encryption and decryption

protocols of XOR-ing bits, given a random key k ∈ K. More formally:

OTP = (E = (k ⊕ m), D = (k ⊕ c)), where, k, m, c ∈ {0, 1}

It is easy to see that the OTP upholds the invariant mentioned earlier:

D(E(k, m)) = k ⊕ E(k, m) = k ⊕ (k ⊕ m) = (k ⊕ k) ⊕ m = 0 ⊕ m = m.

However, the One-time Pad posed weaknesses such as the lack of ability to

re-use keys without loss of security, and the need to have keys as long as the

message. Additionally, the new key that was generated for each communication

needed to be conveyed securely between both communicating parties, leading

to a cyclical problem of security. All these constraints showed the weaknesses

of Symmetric Key Cryptography. Addressing these weaknesses lead to the new

age of Asymmetric Key Cryptography, where the notion of a secret-key and a

public-key emerged. The idea was to have two parties that wanted to commu-

nicate a secret retain a secret-key before communication and then regenerate

numerous public-keys which could be used to compute shared-secrets. The se-

curity provided by such protocols came from the underlying ”one-way” compu-

tational hardness of the group-theoretic problems that formed the backbone of

the protocols. Put another way: These problems were eﬃciently solvable by the

communicating parties, but their inverses were hard to solve, which was made

the task for an adversary hoping to reverse-engineer the system. We analyze

two such cryptosystems: El-Gamal

and RSA

2 El-Gamal Cryptosystem

The El-Gamal Cryptosystem is a method to generate public-keys using a Mul-

tiplicative, Cyclic (Abelian) Group of very large (prime) order. The hardness

of extracting the secret key for such a protocol, given an adversary, comes from

the hardness of the Discrete-Log Problem

. The Discrete-Log Problem is

known to be in BQP (the class of problems computable in Polynomial Time

by a Quantum Computer), and in NP (the class of problems whose positive

solution is veriﬁable in Polynomial Time by a Classical Computer) ∩ co-NP

(the class of problems whose negative solution is veriﬁable in Polynomial Time

by a Classical Computer).

Prerequisites

• G

, where p is a prime. G

is cyclic, multiplicative and abelian. Notice

that G

∼

• g ∈ G

, such that, g = G

. Hence, g is a generator of G

. Notice that

this means ord(g) = ord(G

) = p − 1. Therefore, g

ord(g)

= g

p−1

= 1.

• For the sake of computational purposes, we assume that p is large. It

is feasible to generate large primes in poly(|bits|(p)) (polynomial in the

number of bits of p) time as Primality-Testing

is known to be in P.

With this setup, we can deﬁne the El-Gamal protocol between two parties (say,

Alice & Bob) to generate public keys in a secure manner given the prerequisites.

El-Gamal Protocol (Encryption)

• Alice: Chooses x ∼ G

= Z

= {1, .., p − 1}, where, x =secret-key

Alice

• Alice: Computes g

and sends over (G, p, g

, g) to Bob.

• Bob: Chooses y ∼ G

= Z

= {1, .., p − 1}, where, y =secret-key

Bob

• Bob: Computes g

and sends over (G, p, g

, g) to Alice.

• Alice: Computes (g

)

= g

(abelian) using secret-key

Alice

• Bob: Computes (g

)

= g

using secret-key

Bob

• Bob: Maps message m → m

bob

∈ G

, and then constructs c = m

bob

· g

• Bob: Sends over (c = m

bob

· g

) to Alice.

El-Gamal Protocol (Decryption)

• Alice: Decrypts the message using the shared secret = g

and computing

its inverse: g

−xy

. Then, m

bob

= c · g

−xy

= m

bob

· g

xy−xy

= m

bob

· g

bob

· 1 = m

bob

The underyling fact here is that the calculation of (g

)

−1

is in P (for Alice),

as calculating the modular multiplicative inverse can be accomplished with a

clever use of Euclid’s Divisor Algorithm or Euler’s Theorem. For our analysis,

we will consider the use of the latter.

El-Gamal Protocol (Analysis)

We will show that computing the modular multiplicative inverse is in P, which

allows for eﬃcient decryption. Furthermore, we show that for an adversary

with access to a channel between Alice & Bob, computing the secret keys is

hard (discrete-log problem).

Theorem 1: Decrypting a message in the El-Gamal protocol is in P.

Proof: For decryption to be in P, we need to show that computing (g

)

−1

given (x, g

, |G

| = p−1) is in P, as modular multiplication is computationally

easy.

Notice that g

∈ G

. As G

∼

, we see that, gcd(g

, p) = 1, because every

k < p is relatively prime to a prime number p. This allows us to use Euler’s

Theorem, which states the following:

• Eulers’ Th

: If gcd(a, m) = 1, a

φ(m)

= 1 (mod) m

Letting a = g

, we can use the Theorem to compute (g

)

−1

. Notice that,

in our case, m = p, where p is prime. So, φ(m) = φ(p) = p − 1. Therefore,

)

φ(p)

= 1 mod p. This further reduces to (g

)

p−1

= 1 mod p. Multiplying

by (g

)

−1

= g

−xy

on both sides, we have:

)

p−1

· g

−xy

= g

−xy

mod p =⇒ (g

)

p−1

· (g

)

−1

= (g

)

−1

mod p =⇒

)

p−2

= (g

)

−1

mod p.

This gives us our required inverse: (g

)

−1

= (g

)

p−2

mod p, which can be

computed given (g

, p, G

), all of which are terms that Alice has.

To see that this is P, notice that Alice computes g

from (g

, y) which requires

at most log(y) multiplications, followed by another log(p − 2) multiplications,

which can be computed eﬃciently as well. Given O(log(p)) = |bits|(p) and

O(log(g

)) = |bits|(g

) <= O(log(p)), this Algorithm is run by repeatedly

computing the power of g

, O(log(p)) times. Now, the multiplication takes

Quadratic-Time with respect to the number of bits: O(log(g

))

, and it is re-

peated O(log(p)) times. So, the next complexity is O(log(g

))

· O(log(p)) ≤

O(log(p))

∈ P.

QED

Theorem 2: The El-Gamal protocol is secure, or equivalently, computing x

or y given (G

, p, g

, g

, g) ∈ NP.

Proof: The ﬁrst thing to notice is that merely multiplying g

, g

does not

yield the shared secret g

, but rather yields g

= g

x+y

, which is not used

in the protocol. The only way to construct g

for the adversary is to extract

x, y from the information, and then exponentiate eﬃciently (as shown before).

This means that the adversary needs to compute (log(g

), log(g

)) mod p, and

then exponentiate. However, this reduces to the Discrete-Log problem, which

is known to be in NP. The most eﬃcient algorithm known to compute the

Discrete-Log is the Number-Field Sieve

, which runs in time



O(e

(log(p))

where the tilde hides Poly-logarithmic factors with constants. This guarantees

the security of the encryption and decryption protocol, by guaranteeing the

security of the shared secret (g

), which is used to decrypt the encrypted mes-

sage.

QED

3 RSA Cryptosystem

The RSA Cryptosystem also uses the computational hardness of the underlying

protocol to provide a one-way hard function, where computing the function is in

P in one direction, but in NP in the other direction. The security of the RSA

problem comes from the diﬃculty of Integer Factorization

, which is known

to be in NP. The proof of correctness follows from Fermat’s Little Theorem.

In order to understand the protocol, we must lay the foundations by deﬁning the

Carmichael Tuotient Function, which resembles the Euler Tuotient function in

its multiplicative nature, but diﬀers slightly in using the lcm, thereby becoming

more eﬃcient for computational purposes.

Prerequisites

• Carmichael Tuotient Function λ(n): Gives the smallest integer k, st, a

1 mod n, ∀k < n and (k, n) = 1.

• We know that every n ∈ N can be written as the product of its prime fac-

tors n =



i=1

, where p

→ prime. The multiplicative nature, there-

fore, of the Carmichael Tuotient Function allows us to see that λ(n) =

lcm(λ(p

), .., λ(p

)).

• We notice that λ(n)|φ(n) because the order of Z

= φ(n), and by La-

grange’s Theorem, the order of any element in the group must divide the

order of the group. It is also critical to note that λ(p

) = C · φ(p

) =

C ·φ(p

)

= C ·p

−1

−1), where C = 1/2 if r > 4 and C = 1 otherwise.

With this setup, we can deﬁne the RSA protocol between two parties (say, Alice

& Bob) to generate public keys in a secure manner given the prerequisites.

RSA Protocol (Encryption)

• Alice: Chooses p, q ∼ Z

, st, p, q → prime. This is easy to do as, once

again, Primality-Testing is known to be in P.

• Alice: Constructs n = p · q. Note: This n is equivalent to the n above,

which is merely introduced for the sake of clarity. The integer n is de-

pendent on p, q and not vice-versa. It is clear that p · q is the prime

factorization of n.

• Alice: Eﬃciently computes secret key

Alice

= λ(n) = lcm(λ(p), λ(q)).

• Alice: Chooses e ∼ {1, .., n − 1}, st, gcd(e, λ(n)) = 1. Once again, this

is easily satisﬁed if e → prime, which can be constructed in P using

Primality-Testing.

• Alice: Sends public key

Alice

= e to Bob as: (n, e).

• Bob: Maps message m → m

bob

∈ Z

, and then constructs c = (m

bob

)

mod n.

• Bob: Sends over (c = (m

bob

)

mod n).

RSA Protocol (Decryption)

• Alice: Computes the decryption-key: d = e

−1

mod λ(n). Equivalently,

we need d · e = 1 mod λ(n). As we saw before for the El-Gamal protocol,

given that (e, λ(n)) = 1, we can use Euler’s Theorem to compute d in

Polynomial time (eﬃciently).

• Alice: Computes m

bob

mod n = c

mod n = (m

)

mod n. The correctness

of this statement will be established by Fermat’s Little Theorem.

The underlying goal here is to show that Alice can compute λ(n) eﬃciently,

while an adversary cannot, and that the decryption protocol is correct. This

analysis will borrow the use of Euler’s Theorem for eﬃcient (in P) construction

of an inverse from our previous analysis of the El-Gamal protocol.

RSA Protocol (Analysis)

We will show that attempting to compute λ(n) is ineﬃcient (for the adversary),

that is, it is in NP, thereby, not allowing the adversary to realize the value of d,

given access to e. We will also show that it is eﬃcient for Alice to compute this

value of λ(n), and that the protocol is correct, which will be seen as a corollary

of Fermat’s Little Theorem.

Theorem 1: Decrypting a message in the RSA protocol is in P .

Proof: To prove this, we merely need to show that the construction of d ∈

P for Alice. We note here that m = λ(n) = λ(p · q) = lcm(λ(p), λ(q)) =

lcm(p − 1, q − 1) = (p − 1) · (q − 1) · (1/gcd(p, q)), where, gcd(p, q) can be

eﬃciently (in P) computed using the Euclidean Divisor Algorithm. Now, bor-

rowing from our previous analysis using Euler’s Theorem, the inverse of e

mod m becomes e

m−2

mod m which, on substituting for m, yields: (e

λ(n)−2

)

mod λ(n) = (e

(p−1)·(q−1)·(1/gcd(p,q))−2

) mod λ(n) = d mod λ(n), which (again,

by our previous analysis) is in P. This follows because Z

λ(n)

is a multiplicative,

abelian group.

Theorem 2: Decrypting a message in the RSA protocol is in-feasible, or equiv-

alently, computing d given (e, n) ∈ NP for an adversary.

Proof: The goal of the adversary is to decrypt c = (m

bob

)

mod n, given (e, n).

Note that, in order to do this, the adversary needs to compute λ(n), otherwise

the adversary cannot construct d. To do so, the adversary needs to prime-

factorize λ(n) = lcm(



i=1

(λ(p

))

. The adversary, however, has no knowledge

of p, q, which are chosen at random. Therefore, the adversary must construct

the Integer Factorization of n. However, it is known to be the case that Integer-

Factorization ∈ NP.

Theorem 3: (e, λ(n)) = 1 ∧ d · e = 1 mod λ(n) =⇒ (m

)

mod n =

Proof: This proof relies on Fermat’s Little Theorem, which states the fol-

lowing:

• Fermat’s Little Theorem: Given p → prime, st, p  |a, a

p−1

= 1 mod p.

Noticing that λ(n) = lcm(p − 1, q − 1), we see that, λ(n) = a(p − 1) and

λ(n) = b(q−1) for some a, b ∈ Z. As d·e = 1 mod λ(n), we see that λ(n)|(ed−1).

Noticing that λ(n) can be expressed as multiples of (p − 1) and (q − 1), we can

conclude via transitivity that (p − 1)|(ed − 1) and (q − 1)|(ed − 1). This allows

us to evaluate (m

)

mod p and (m

)

mod q. We can then compute (m

)

mod pq by multiplying the LHS and the RHS. Let, (ed − 1) = a



(p − 1) and

(ed − 1) = b



(q − 1) for some a



, b



∈ Z. Then:

• (m

)

mod p = (m

ed−1

) · m mod p = m



(p−1)

· m mod p. By Fermat’s

little theorem, (m

p−1

)



mod p = 1 mod p. Therefore, m



(p−1)

· m mod

p = m mod p.

• Similarly, (m

)

mod q = (m

ed−1

) · m mod q = m



(q−1)

· m mod q. Using

Fermat’s Little Theorem again, we see that m



(q−1)

· m mod q = m mod

• Given that m

mod p = m mod p and m

mod q = m mod q, a direct,

modular multiplication yields that m

mod pq = m mod pq = m mod n.

This proves that d is the decryption key to recover the ciphertext and establishes

the correctness of the RSA decryption protocol.

Conclusion and Further-Work

It is evident from the above analysis that the subtle interplay between Algebra

and Complexity gives rise to the desired security properties for the aforemen-

tioned protocols. The centrality of Group-Theoretic constructions to the most

widely used Key-Generation protocols in Asymmetrical-Key Cryptography is

undeniable. Over the years, many more Asymmetrical Key Generation proto-

cols have been developed, with a current trend of shifting more towards Lattice-

Based Cryptography. Exploring the recent developments in this area would

make for an educational survey. Other interesting developments in recent years

have included the study of Homomorphic Encryption and the resilience (or lack

thereof) of Asymmetrical Key Generation protocols to Quantum adversaries.

Acknowledgements

I would like to thank Dr. Martinez immensely for his impeccable teaching, never-

ending guidance and the numerous deep conversations about the intersections

of Pure Math, Theoretical Computer Science and Mathematical Physics. In

particular, his contribution of pushing me to write a survey exploring the inter-

sections between Cryptography & Algebra was the starting point for this work,

and I owe it unanimously to him. I would also like to thank Lily (Jisoo) Jeong

for helping me settle down on a viable list of topics to pursue and for generously

agreeing to provide feedback on the manuscript.

Reference

1. Hoskisson, P. (2010). Breakthrough Translation of Avicenna’s Physics

Published. INSIGHTS, Volume 30, No. 1, 1-4.

2. Rijmenants, D. (2004). Technical Details of the Enigma Machine, Cipher

Machines And Cryptology.

3. Jarecki, S. (09/28/2004). Lecture 1: Crypto Overview, Perfect Secrecy,

One-time Pad.

4. Goldwasser, S & Bellare, M. (2008). 10.3.3 El Gamal’s Scheme. Lecture

Notes of Cryptography, 171-172.

5. Goldwasser, S & Bellare, M. (2008). C.8 RSA. Lecture Notes on Cryptog-

raphy, 262-263.

6. Pomerance, C (2009). Discrete Logarithms, Dartmouth College.

7. Schoof, R. (2008). Four Primality Testing Algorithms. Algorithmic Num-

ber Theory, Volume 44, 101-126: MSRI Publications

8. Schirokauer, O. (2008). The impact of the number ﬁeld sieve on the

discrete logarithm problem in ﬁnite ﬁelds. Algorithmic Number Theory,

Volume 44, 397-420: MSRI Publications

9. Bimpikis, K & Jaiswal, R. Modern Factoring Algorithms, UC San Diego.