Introduction to Computational Number Theory in Cryptography
Cryptography
Lecture 18
(Computational)
number theory
Why now?
•
We have not needed any number theory or
“advanced math” until now
–
Practical private-key cryptography is based on
stream ciphers, block ciphers, and hash functions
–
Lots of interesting and non-trivial crypto can be
done without any number theory!
Why now?
•
Reason 1: Culmination of “top-down”
approach
–
For most cryptography, we ultimately need to
assume some problem is hard
–
The “lowest-level” assumptions we can make
relate to problems in number theory
–
These problems have often been studied a long
time
Why now?
•
Reason 2: The public-key setting
–
Public-key encryption
requires
number theory (in
some sense)
Our goal
•
Cover basic number theory quickly!
•
Cover the minimum needed for all the
applications we will study
–
Some facts stated without proof
–
Can take entire class(es) devoted to this material
•
Abstracting some of the ideas makes things
easier to understand
Computational
number theory
•
We will be interested in the computational
difficulty of various problems
–
Different from most of mathematics!
•
The
representation
of mathematical objects is
crucial for understanding the computational
efficiency of working with them
Computational
number theory
•
Measure running times of algorithms in terms
of the
input lengths
involved
–
For integer x, we have ǁxǁ = O(log x), x = O(2
ǁxǁ
)
•
An algorithm taking input x and running in
time O(x) is
exponential
time
–
Efficient algorithm must run in time poly(ǁxǁ)
Computational
number theory
•
Our goal: classify various problems as either
“easy” or “hard”
–
I.e., polynomial-time algorithms known or not
•
We will not focus on optimizations, although
these are very important in practice
–
For “easy” problems: speed up cryptographic
implementations
–
For “hard” problems: need to understand concrete
hardness for concrete security
Representing integers
•
Cryptography involves very large numbers!
•
Standard (unsigned) integers (e.g., in C) are small,
fixed length (e.g., 16 or 32 bits)
–
For crypto, need to work with integers that are much
longer (e.g., 2000 bits)
•
Solution: use an
array
–
E.g., “bignum” = array of unsigned chars (bytes)
–
May be useful to also maintain a variable indicating
the length of the array
–
Or, assume fixed length (which bounds the maximum
size of a bignum)
Example: addition
•
Now need to define all arithmetic operations
on bignums
•
Start by adding two bytes (e.g., bignum arrays
of length 1)
–
Note that C discards the overflow, i.e., it does
addition modulo 2
8
Example: adding bytes
•
AddWithCarry(char a, char b, char carry)
// carry is 0 or 1
–
If a < 2
7
and b < 2
7
res=a+b+carry, carry=0
–
If a ≥ 2
7
and b ≥ 2
7
res=(a-2
7
)+(b-2
7
)+carry, carry=1
–
If a < 2
7
and b ≥ 2
7
res=a+(b-2
7
)+carry
•
If res ≥ 2
7
res=res-2
7
, carry=1
•
Else res=res+2
7
, carry=0
•
Note a ≥ 2
7
iff msb(a)=1
Example: addition
•
Add(bignum a, int L1, bignum b, int L2)
–
Use grade-school addition, using AddWithCarry
entry-by-entry…
•
Running time O(max{L1,L2}) = O(max{ǁaǁ,ǁbǁ})–
If ǁaǁ=ǁbǁ=n then O(n)
–
Is it possible to do better?
•
No – must read input (O(n)) and write output (O(n))
Example: multiplication
•
What is the length of the result of a*b?
–
ǁabǁ=O(log ab)=O(log a + log b) =O(ǁaǁ+ǁbǁ)
•
Use grade-school multiplication…
•
Running time O(ǁaǁ
ǁbǁ)
–
If ǁaǁ=ǁbǁ=n then O(n
2
)
–
Can we do better?
•
Surprisingly…yes! But we will not cover here…
Basic arithmetic operations
•
Addition / subtraction / multiplication can all
be done efficiently
–
Using grade-school algorithms (or better)
•
Division-with-remainder can also be done
efficiently
–
Much less obvious!
Modular arithmetic
•
Notation:
–
[a mod N] is the remainder of a when divided by N
–
Note 0 ≤ [a mod N] ≤ N-1
•
a = b mod N
[a mod N] = [b mod N]
Modular arithmetic
•
Note that
[a+b mod N] = [[a mod N] + [b mod N] mod N]
[a-b mod N] = [[a mod N] - [b mod N] mod N]
and
[ab mod N] = [[a mod N][b mod N] mod N]
•
I.e., can always work with reduced
intermediate values
–
This can be used to speed up computations
Modular arithmetic
•
Careful: not true for division!
•
I.e., [9/3 mod 6] = [3 mod 6] = 3
but [[9 mod 6]/[3 mod 6] mod 6] = 3/3 = 1
–
We will return to division later…
Modular arithmetic
•
Modular reduction can be done efficiently
–
Use division-with-remainder
•
Modular addition / subtraction /
multiplication can all be done efficiently
–
We will return to division later
Exponentiation
•
Compute a
b
?
–
ǁa
b
ǁ = O(b · ǁaǁ)
–
Just writing down the answer takes
exponential
time!
•
Instead, look at
modular
exponentiation
–
I.e., compute [a
b
mod N]
–
Size of the answer < ǁNǁ
–
How to do it?
•
Computing a
b
and then reducing modulo N will not work…
Hash functions
(Not covered in Spring 2020)
Recall: building a hash function
•
Two-stage approach
–
Build a
compression function
h
•
I.e., hash function for
fixed-length inputs
–
Build a full-fledged hash function (for arbitrary
length inputs) from a compression function h
•
We have already discussed how to do the
second step (Merkle-Damgard transform)
Building a compression function
•
Davies-Meyer construction
–
Others are also possible
•
h(k, m) = F
k
(m)
m
F
k
m
Proof of security?
•
Can prove collision resistance if we model the
underlying block cipher F as an
ideal cipher
–
Stronger than the random-oracle model!
•
Model block cipher F: {0,1}n
x {0,1}n
{0,1}n
as a collection of public, independent, random
permutations
–
I.e., for each key k, F
k
is an independent, random
permutation on {0,1}n
The ideal-cipher model
•
This is
more
than assuming F is a PRP
–
F
k
random
even when k is known
!
–
No weak keys (i.e., F
k
random even when k is not
uniform)
–
No related-key attacks (i.e., F
k
and F
k’
are independent
even when k, k’ are related)
•
Formally, similar to the RO model
–
In particular, the only way to evaluate F is via explicit
oracle queries
–
Attacker allowed to query F and F
-1
Proof of security
•
Claim: attacker making q queries finds a
collision with probability
q
2
/2
n
(optimal)
•
Proof
–
Each query to F/F
-1
reveals one value h
i
= h(k
i
,m
i
)
•
Moreover, each h
i
is (essentially) uniform and
independent of all previous outputs
–
So probability of finding a collision is (essentially)
the same as for a birthday attack
SHA-2
•
Compression function based on Davies-Meyer
–
With “block cipher” specifically designed for SHA
•
Hash function built from compression function
using Merkle-Damgard
Practical private-key cryptography can be done without advanced math, but understanding computational number theory is essential for public-key encryption. This field focuses on the computational difficulty of problems, analyzing algorithms' running times, classifying problems as easy or hard based on polynomial-time algorithms, and the efficiency of mathematical object representations in computations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Cryptography Lecture 18
(Computational) number theory
Why now? We have not needed any number theory or advanced math until now Practical private-key cryptography is based on stream ciphers, block ciphers, and hash functions Lots of interesting and non-trivial crypto can be done without any number theory!
Why now? Reason 1: Culmination of top-down approach For most cryptography, we ultimately need to assume some problem is hard The lowest-level assumptions we can make relate to problems in number theory These problems have often been studied a long time
Why now? Reason 2: The public-key setting Public-key encryption requires number theory (in some sense)
Our goal Cover basic number theory quickly! Cover the minimum needed for all the applications we will study Some facts stated without proof Can take entire class(es) devoted to this material Abstracting some of the ideas makes things easier to understand
Computational number theory We will be interested in the computational difficulty of various problems Different from most of mathematics! The representation of mathematical objects is crucial for understanding the computational efficiency of working with them
Computational number theory Measure running times of algorithms in terms of the input lengths involved For integer x, we have x = O(log x), x = O(2 x ) An algorithm taking input x and running in time O(x) is exponential time Efficient algorithm must run in time poly( x )
Computational number theory Our goal: classify various problems as either easy or hard I.e., polynomial-time algorithms known or not We will not focus on optimizations, although these are very important in practice For easy problems: speed up cryptographic implementations For hard problems: need to understand concrete hardness for concrete security
Representing integers Cryptography involves very large numbers! Standard (unsigned) integers (e.g., in C) are small, fixed length (e.g., 16 or 32 bits) For crypto, need to work with integers that are much longer (e.g., 2000 bits) Solution: use an array E.g., bignum = array of unsigned chars (bytes) May be useful to also maintain a variable indicating the length of the array Or, assume fixed length (which bounds the maximum size of a bignum)
Example: addition Now need to define all arithmetic operations on bignums Start by adding two bytes (e.g., bignum arrays of length 1) Note that C discards the overflow, i.e., it does addition modulo 28
Example: adding bytes AddWithCarry(char a, char b, char carry) // carry is 0 or 1 If a < 27and b < 27res=a+b+carry, carry=0 If a 27and b 27res=(a-27)+(b-27)+carry, carry=1 If a < 27and b 27res=a+(b-27)+carry If res 27res=res-27, carry=1 Else res=res+27, carry=0 Note a 27iff msb(a)=1
Example: addition Add(bignum a, int L1, bignum b, int L2) Use grade-school addition, using AddWithCarry entry-by-entry Running time O(max{L1,L2}) = O(max{ a , b }) If a = b =n then O(n) Is it possible to do better? No must read input (O(n)) and write output (O(n))
Example: multiplication What is the length of the result of a*b? ab =O(log ab)=O(log a + log b) =O( a + b ) Use grade-school multiplication Running time O( a b ) If a = b =n then O(n2) Can we do better? Surprisingly yes! But we will not cover here
Basic arithmetic operations Addition / subtraction / multiplication can all be done efficiently Using grade-school algorithms (or better) Division-with-remainder can also be done efficiently Much less obvious!
Modular arithmetic Notation: [a mod N] is the remainder of a when divided by N Note 0 [a mod N] N-1 a = b mod N [a mod N] = [b mod N]
Modular arithmetic Note that [a+b mod N] = [[a mod N] + [b mod N] mod N] [a-b mod N] = [[a mod N] - [b mod N] mod N] and [ab mod N] = [[a mod N][b mod N] mod N] I.e., can always work with reduced intermediate values This can be used to speed up computations
Modular arithmetic Careful: not true for division! I.e., [9/3 mod 6] = [3 mod 6] = 3 but [[9 mod 6]/[3 mod 6] mod 6] = 3/3 = 1 We will return to division later
Modular arithmetic Modular reduction can be done efficiently Use division-with-remainder Modular addition / subtraction / multiplication can all be done efficiently We will return to division later
Exponentiation Compute ab? ab = O(b a ) Just writing down the answer takes exponential time! Instead, look at modular exponentiation I.e., compute [abmod N] Size of the answer < N How to do it? Computing aband then reducing modulo N will not work
Hash functions (Not covered in Spring 2020)
Recall: building a hash function Two-stage approach Build a compression function h I.e., hash function for fixed-length inputs Build a full-fledged hash function (for arbitrary length inputs) from a compression function h We have already discussed how to do the second step (Merkle-Damgard transform)
Building a compression function Davies-Meyer construction Others are also possible h(k, m) = Fk(m) m m k F
Proof of security? Can prove collision resistance if we model the underlying block cipher F as an ideal cipher Stronger than the random-oracle model! Model block cipher F: {0,1}n x {0,1}n {0,1}n as a collection of public, independent, random permutations I.e., for each key k, Fk is an independent, random permutation on {0,1}n
The ideal-cipher model This is more than assuming F is a PRP Fk random even when k is known! No weak keys (i.e., Fk random even when k is not uniform) No related-key attacks (i.e., Fk and Fk are independent even when k, k are related) Formally, similar to the RO model In particular, the only way to evaluate F is via explicit oracle queries Attacker allowed to query F and F-1
Proof of security Claim: attacker making q queries finds a collision with probability q2/2n (optimal) Proof Each query to F/F-1 reveals one value hi = h(ki ,mi) Moreover, each hi is (essentially) uniform and independent of all previous outputs So probability of finding a collision is (essentially) the same as for a birthday attack
SHA-2 Compression function based on Davies-Meyer With block cipher specifically designed for SHA Hash function built from compression function using Merkle-Damgard
