Week 3 Lecture
Cryptography II:
Public Key Encryption: Part 1 – Concept and Maths
Principles for CONFIDENTIALITY
Copyright By PowCoder代写 加微信 powcoder
FIT2093 INTRODUCTION TO CYBER SECURITY
www.monash.edu
Last lecture (week 2) — Symmetric Key Encryption
This week (week 3):
• Public Key Encryption – PKE (aka Asymmetric key Encryption)
• Why do we need public key cryptography?
• The concept of public key cryptography
• Maths of PKE
• The math behind public key cryptography: number theory
Next Week (week 4): How PKE Algorithms work
• Diffie-Hellman key exchange & ElGamal encryption
• RSA encryption
Public Key Encryption (PKE)
Symmetric Key Encryption (SKE): limitation
Public Key Crypto
● both sides share same secret key ● Q: how to share a key privately?
○ keydistributionproblem
Symmetric Key Encryption (SKE): limitation
Public Key Crypto
● key distribution problem: ○ howtoshare?
■ farapart/nevermetbefore/channelinsecure ○ Q:whyneedtosharekeyprivately?
Public Key Encryption (PKE)
Public Key Crypto
● Idea of PKE (Diffie-Hellman 1976): Make the encryption key public
● Encrypt with one key (public key), decrypt with another key (private key) ● no need to share privately (no private key distribution problem)
● public key need not be kept secret
PKE vs SKE
Public Key Crypto
Each user has a
public key pk & private key sk;
pk & sk are mathematically related
Each user privately shares a secret key k with another
Do with pk, undo with sk
Do and undo with k
No Key Distribution Problem
Key Distribution Problem
Slower. Q: Why?
PKE Requirements
Public Key Crypto
● Functionality: easy for good guys
○ generate key pair pk & sk
○ encrypt, decrypt
● Security: computationally infeasible for bad guys
○ get sk from pk
○ get message P from C and pk
Maths of PKE
Maths of PKE
Public Key Crypto
● Why does PKE need maths? ○ twokeysneedtoberelated
• do with one, undo with another
● Why SKE no need maths? ○ nosuchrequirement
● What type of maths? ○ numbertheory
○ whynumbertheory?
Maths of PKE
Public Key Crypto
● Why PKE needs number theory? ○ twokeysneedtoberelated
• s.t. do with one, undo with another
• usepktogetC
• use sk to “cancel out” pkfrom C , to get back P
• yet knowing pk, cannot compute the sk
• should have one-way function from sk to pk
● we recap on high school maths, and a little bit more 11
Maths of PKE
Public Key Crypto
● Commonly used PKE algorithms (next week’s lecture): ○ based on discrete logarithm problem (DLP)
• e.g. ElGamal Encryption [ElGamal 1994]
○ based on Integer Factorisation Problem (IFP)
• e.g. RSA Encryption [Rivest, Shamir, Adleman 1977] Both based on number theory problems!
So, let’s learn a little about those…
The Maths behind PKE
Number Theory
What type of maths is useful for PKE?
○ Number Theory: playing with integers (0,1,2,3,…) ○ Brief History:
○ Ancient times to 1970s: numerous beautiful discoveries ○ But no known practical uses (for mathematicians only)!
○ 1970s: Unexpected discovery of use in cryptography ○ How to build a PKE!
○ 1980s – now: numerous new ”impossible sounding” applications in cryptography
○ E.g. homomorphic encryption: how to compute on encrypted data without decrypting it (will not cover here, useful for, e.g. private outsourcing of computation to the cloud)
Integers … revision Public Key Crypto
● Awholenumberincludingitsnegativeand0, ○ Examples:1,5,−2,100,etc.
● Hasbasicmathematicalpropertiese.g.
○ Adding/Multiplying2integersgivesanintegertoo ○ Adding/Multiplying:orderdoesnotmatter
○ Add0/Multiply1:nothingchanges
○ Inverse for Add: −x
○ Inverse for Mul: 1/x (but not integer)
Prime vs Composite numbers
Public Key Crypto
● Primenumber
○ hasexactlytwo(distinct)divisors/factors,whichare1andthe(prime)
number itself
○ Example:2,3,5,7,11,13,17,19,…
● Compositenumber(theopposite)
○ hasatleastonepositivedivisorotherthan1anditself ○ Example:4has1,2and4aspossibledivisors
● Number0and1arespecialnumbers.Theyarenotconsideredasprimeor composite numbers
Prime Numbers
Public Key Crypto
● Listofprimenumbersp<200
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83
89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199
Factor (divisor) Public Key Crypto
● xisfactorofnifncandividexwithoutremainder(R=0)
● Examples:
○ 2 is a factor of 4 because
• 4 ÷ 2 = 2 (quotient), remainder 0 ○ 2 is not a factor of 9 because
• 9 ÷ 2 = 4 (quotient) and remainder = 1 ● Trivial factor (not interesting, it’s obvious)
○ A trivial factor of an integer n is the number 1 and the number n itself
# Interesting Factors
Public Key Crypto
● Definition:non-trivialfactor=factorthat’snottrivial ○ moreinteresting(not1anditself)
● Example:fornumber6,
○ 1 and 6 are the trivial factors,
○ 2 and 3 are non-trivial factors
○ since 2 & 3 are prime, we call them prime factors:
• They don’t decompose into smaller factors
Integer Factorisation
Public Key Crypto
● breakdownacomposite(itcannotbeprime)numberintosmallernon- trivial factors
○ i.e.findthefactors
● Examples: ○ 6=2x3
○ 12=2x2x3 ○ 18=2x3x3
# Integer Factorisation Problem
Public Key Crypto
● Primefactorisation
○ find the prime factors of n, may appear multiple times ○ factoringnasaproductofprimepowers
•15=3x5, 24=23x3
• 3600=24x32x52
● Theorem(PrimeFactorisation):Everyintegercanbefactoredintoa
product of prime powers in a unique way
● IntegerfactorisationProblem:Givenanintegern,computetheprime
factorisation of n
# Integer Factorisation Problem
Public Key Crypto
● IntegerFactorisationProblem(IFP):Givenanintegern,computethe prime factorisation of n
● Gist:itdefinitelyexists(duetotheproventheorem), just find it (the prime factors)
Q: What is the prime factorisation of 63?
Integer Factorisation Problem: Computational Difficulty Public Key Crypto
Integer factorisation Problem (IFP): Given an integer n, compute the prime factorisation of n
• Do one direction (opposite to IFP) is easy: multiply numbers ▪ Givenprimefactorsofn,multiplyfactorstogetn
▪ primaryschoolmaths
• Do other direction (IFP) is computationally difficult: factor ▪ Factorlargenumbernisharderthanmultiplying
▪ somealgorithmsexistbutnotefficient
Q: How do we measure efficiency of algorithms? 22
Is an Algorithm Efficient? Public Key Crypto
● TimeT(ornumberofsteps)torunalgorithm,dependson
○ Lengthlen(n)ofinputi.e.howmanydigits/bitsthatnhas
● Examples
● Decimal(base10):
○ len10(3) = 1
○ len10(34) = 2 ● Binary(base2):
○ len2(3) = len2(112) = 2
○ len2(34) = len2(1000102) = 6
Is Algorithm Efficient? Public Key Crypto
● Efficientalgorithm:
○ T = polynomial function of len(n)
○ e.g. multiply two 3-digit numbers n=456 and m=123
456 so len(n) = len(m) = 3 x 123
T = 9 steps = 32 = len(n)2
Is Algorithm Efficient? Public Key Crypto
Integer Factorisation is Computationally Difficult Public Key Crypto
Integer Factorisation is Computationally Difficult Public Key Crypto
• Strategy: how to use infeasible integer factorisation problem for PKE?
○ Do encryption so that attacking requires factorisation
○ used to get the security for RSA encryption (next week)
Greatest Common Divisor (GCD)
Public Key Crypto
● largestpositiveintegerthatcandividetwointegerswithoutleavingaremainder ● Examples:
○ GCD of numbers 6 and 9: GCD(6,9) = 3
• The greatest common factor = 3 = GCD(6, 9)
○ GCD of integers 48 and 64: GCD(48,64) = 16
• 48=2x2x2x2x3=16x3=8x 6=4x12=2x24
• 64=2x2x2x2x2x2=8x8=16x4=32x2
• GCD (48, 64) = 16
Surprising Fact: There’s an efficient algorithm for computing GCD.
• Called Euclid’s algorithm (we won’t study)-- no need to factor integers!
Relatively Prime / Co-Prime Public Key Crypto
● Twonumbersx,yarerelativelyprime ○ ifGCD(x,y)=1
● Examples:
○ 5 and 6 are relatively prime since GCD(5,6) = 1 ○ 6 and 9 are not relatively prime because
GCD (6,9) = 3
• Both 6 and 9 can be divided by 3 without leaving any remainder
Q: What is the GCD of 28 and 25? Are they relatively prime? How about 66 and 44?
Modular Arithmetic Public Key Crypto
● Modulararithmetic=clockarithmetic
● Clockhas12numbers,forwhateverthenumber,restartafter12stepsi.e.
e.g. 14.00 hours ≡ 2 PM 14 mod 12 ≡ 2
14 ≡ 2 (mod 12)
• 14 and 2 occupy the same position in the 12-hrs clock
• 14 and 2 are congruent modulo 12
Modular Arithmetic Public Key Crypto
● Examples
○ 25mod12= 1,25≡1(mod12)
○ 9mod3 = 0, 9≡0(mod3) ○ 10mod3 = 1,10≡1(mod3)
○ 12mod7 =5, 12≡5(mod7) ○ 9mod7 =2 9≡2(mod7)
Modular Arithmetic Public Key Crypto
Modular Arithmetic Trick Public Key Crypto
● (c+d)modn≡(cmodn+dmodn)modn
○ add then mod
○ Is equivalent to,
○ mod each, then add and mod
● Example:
○ (2+14)mod12≡?
○ It can be calculated as:
• 16mod12≡4
• (2mod12+14mod12)mod12 ≡ ( 2 + 2 ) mod 12 ≡ 4
Q: What is 42 + 45 mod 15? Use the mod addition trick.
Modular Arithmetic Trick Public Key Crypto
● (c+d)modn≡(cmodn+dmodn)modn
○ add then mod
○ Is equivalent to,
○ mod each, then add and mod
● AnotherExample:
○ (12+9)mod7≡?
○ Itcanbecalculatedas:
• 21mod7≡0
• (12mod7+9mod7)mod7 ≡ ( 5 + 2 ) mod 7 ≡ 0
Modular Arithmetic Public Key Crypto
Modular Subtraction Public Key Crypto
● (c–d)modn≡(cmodn+(–d)modn)modn ○ minusthenmod,
○ Isequivalentto
○ modeachthenminusandmod
● Example:
○ (2–18)mod12≡?
● Can be calculated as
○ –16mod12≡–4
○ (2mod12+(–18)mod12)mod12 ≡ (2 + (–6)) mod 12 ≡ –4
Q: What is 42 - 88 mod 15? Use the mod subtraction trick.
Modular Multiplication Public Key Crypto
● Example:
(5 * 14) mod 12 ≡ ? Can be calculated as:
70 mod 12 ≡ 10 OR
(5 mod12*14mod12)mod12 ≡ (5 * 2) mod 12 ≡ 10
Q: What is 42 x 77 mod 15? Use the mod multiply trick.
Multiplicative Inverse mod n
Public Key Crypto
• Multiplicative inverse of integer a -- regular (not modular) arithmetic: • A numberb,denotedbya-1(or1/a)suchthataxb=1
• Example:a=5,b=5-1=1/5=0.2
• a-1 is a fraction (not an integer)
Multiplicative inverse of integer a -- modular arithmetic mod n: • Similar, but a-1 mod n is an integer b < n
• Multiplicative inverse of integer a mod n
• Numberb,denotedbya-1modn,suchthataxbmodn=1 • Examples:
• a=5,n=7:b=5-1mod7=3 Q:Whatis3-1mod11?
• check:5x3mod7=15mod7=1 • a=2,n=9:b=2-1 mod9=5
• check:2x5mod9=10mod9=1
Multiplicative Inverse mod n
Public Key Crypto
How to divide mod n with modular inverse
• In normal (not modular) arithmetic, a ÷ b = a x b-1 • Examples
• 2÷5=2x5-1 =2x0.2=0.4 • 8÷2 = 8x2-1=8x0.5=4
• Inmodulararithmeticmodn,a÷bmodn=axb-1modn • Examples
• 2÷5mod7=2x5-1 mod7=2x3mod7=6 • (check: 6x5 mod7=30mod7=2)
• 8÷2 mod9= 8x2-1mod9 =8x5mod9=40mod9=4 • (check:4x2mod9=8mod9=8).
When does no multiplicative inverse exist? Public Key Crypto
In normal (not mod arithmetic),
• Inverse of 0 (1/0 = 0-1) does not exist
• cannot divide by 0!
àThere is no number b such that b x 0 = 1
In modular arithmetic mod n,
• a-1 mod n does not exist if a has common factor > 1 with modulus n (i.e if a
not relatively prime to n) • Example:
• n=12,a=4:GCD(4,12)=4>1. • So 4-1 mod 12 does not exist!
Modular Division vs Multiplicative Inverse Public Key Crypto
● Theorem:ExistenceofMultiplicativeInverseofdmodn (s.t.d*d–1 modn=1)
when d and n are relatively prime,
d has a multiplicative inverse mod n, usually denoted by d-1
Fact: If d and n are relatively prime, there’s an efficient algorithm – Extended Euclid’s algorithm (we won’t study it) — to compute d–1 mod n
Integer Exponentiation Public Key Crypto
ae = a×a×a×a×a×…×a
Modular Exponentiation: Square & Multiply Algorithm Public Key Crypto
Square&MultiplyAlgorithm: aemodn,e.g.75mod11(a=7,e=5,n=11)
Decompose exponent in binary representation: e = 510 = 1012
Start from Most Significant (leftmost) bit of e (always 1), set z = a.
For each subsequent bit bi of e:
• Ifbitbi =0,justsquarez,i.e.setz=z2 modn
• Ifbitbi =1,squarezandmultiplyitbya,i.e.setz=z2 xamodn
75 mod 11 example:
• StartwithMSbitb2=1ofe=1012 ,setz=a=7.
• I=2:bitb1=0àsquare:z=z2 modn=72 mod11=5
• i=1:bitb0=1àsquare&multiply:z=z2 xamod11=52 x7mod11=3x7mod11=10
More Examples
412 mod 13:
• StartwithMSbitb3=1ofe=1210 =11002 ,setz=a=4.
• i=2:bitb2=1àsquare&multiply:z=z2 xamodn=42 x4mod13=12
• i=1:bitb1=0àsquare:z=z2 modn=122 mod13=1
• i=0:bitb0 =0àsquare:z=z2 modn=12 mod13=1.àSo412mod13=1
511 mod 7:
• StartwithMSbitb3=1ofe=1110 =10112 ,setz=a=5.
• i=2:bitb2=0àsquare:z=z2 modn=52 mod7=4
• i=1:bitb1=1àsquare&multiply:z=z2 xamodn=42 x5mod7=3
• i=0:bitb0 =1àsquare&multiply:z=z2 xamod7=32 x5mod7=3.àSo511mod7=3
Modular Exponentiation: Square & Multiply Algorithm Public Key Crypto
Discrete Log Problem (DLP) Public Key Crypto
● DiscreteLogarithm:thereverseoperationofmodularexponentiation ● Infeasibletosolvewithknownalgorthims
● DLP:Givenb=aemodn,a&n,computeexponente
● Knownalgorithms:inefficient,infeasible
○ brute force: time T ~ exponential in len(n)
○ DLP Number Field Sieve: time is sub-exponential in len(n)
● DesignStrategyforPublic-KeyEncryption,crypto
○ do encryption/etc so that attacking requires solving DLP
○ usedforsecurityguaranteesofDiffie-Hellman,ElGamal,…
Euler’s Totient function(n) … for RSA Public Key Crypto
● Example:n=10
○ Residues = numbers < n: {0,1,2,3,4,5,6,7,8,9}
○ Residues relatively prime to n: {1,3,7,9}
● Euler’sTotientfunctionø(n)=numberofresiduesrelativelyprime(i.e. GCD =1) to n
Euler’s Totient function ø(n) for prime n Public Key Crypto
● Ifnisaprimenumber,thenø(n)=n–1 ○ Example:
• n=3, ø(3) = 3–1 = 2, i.e. the numbers {1,2}
• n=5, ø(5) = 5–1 = 4, i.e. the numbers {1,2,3,4}
ø(n)for product of two primes p & q Public Key Crypto
● Ifnisproductofprimenumbersp,qthen ○ ø(n) = (p–1)(q–1)
● Example:
○ ø(n) = ø(p*q) = (3–1)*(7–1) = 12 i.e. the numbers {1,2,4,5,8,10,11,13,16,17,19,20}
Q: What is ø(15)?
Euler’s Theorem & Fermat’s Little Theorem Public Key Crypto
● Euler’sTheorem:IfMandnarerelativelyprime,then ○ Mø(n) modn=1
○ so Mø(n)+1 mod n = M (used for RSA)
Fermat’s Little Theorem: If p is a prime number and M is relatively prime to p, then
○ Mø(n) mod p =Mp–1 modp=1
Euler’s Theorem: Examples
Public Key Crypto
Euler’s Theorem: Mø(n) mod n = 1 • n=21,M1 =5,M2 =8
ø(21) = (3-1) x (7-1) = 2 x 6 = 12 (because 21 = 3 x 7); So by Euler’s Theorem:
• M1ø(n)modn=5ø(21)mod21=512mod21=1. • M1ø(n)modn=8ø(21)mod21=812mod21=1.
Fermat’s Little Theorem: Examples
Public key Crypto
Fermat’s Little Theorem: Mp-1 mod p = 1
p = 7 , M1 = 2, M2 = 3:
• M1ø(n)modp=26 mod7=64mod7=1
• M2ø(n)modp=36 mod7=27x27mod7 =6x6mod7=1
Euler’s Theorem: for RSA decryption Public Key Crypto
● RecallagainEuler’sTheorem:IfMandnarerelativelyprime, then
○ Mø(n) modn=1
Implication of Euler’s Theorem:
● Ifymodø(n)=1thenMymodn=M
• Sincey=ø(n)xk+1forsomeintegerkthen • Mymodn=Mø(n)xk+1 modn
=(Mø(n))modn)k xM1 modn=1k xM1 modn=M
Implication of Euler’s Theorem: Examples
Public key Crypto
Implication of Euler’s Theorem: My mod n = M if y mod ø(n) = 1 n=21,M1 =5,M2 =8, y=13:
ymodø(n)= 13mod12=1so:
• M1ymodn=513mod21=5. • M2ymodn=813mod21=8.
How to Find Large Prime Numbers?
Public Key Crypto
● ForPKE,needtoefficientlygeneratelargerandomprimenumbers
● Q1:howtocheckifpisprime,efficiently?
○ brute-force primality check: divide p by all integers up p
T ~ exponential – inefficient
○ Fact (Miller- Testing): There is an efficient algorithm for
primality testing (no trial division)
○ Idea of Miller-Rabin (we won’t study): use Fermat’s Little Theorem for p • choose many random a, check if ap–1 mod p = 1
How to Find Large Prime Numbers?
Public Key Crypto
● ForPKE,needtoefficientlygeneratelargerandomprimenumbers
● Q2:IfwechoosearandomL-bitintegerp,what’sthechancethatpisprime?
○ If chance small, need to repeat primality test on too many random integers until find a prime integer
○ Luckily, chance is not too small:
○ Theorem (Prime Number Theorem): For large L, the fraction of integers of bit length up to L
that are prime, is close to 1 / (0.693*L)
● Example: On average, we should find a prime after testing about 693 random 1000-bit integers
How to Find Large Prime Numbers?
Public Key Crypto
● Conclusion (Q1+Q2):
○ It’s possible to efficiently generate large random prime integers
○ Just keep picking random integers and test them for primality until a prime is found
Summary: Feasible and Infeasible Problems
Public Key Crypto
Feasible Problems (efficient algs.) (Used in PKE by honest parties)
Infeasible Problems (inefficient algs.) (for PKE security against attacks)
Integer Multiplication
Integer Factorisation Problem (IFP)
Modular Exponentiation
Discrete Logarithm Problem (DLP)
Greatest Common Divisor (GCD)
Multiplicative inverse mod n
Finding large random primes
Further Reading
Public Key Crypto
Section 2.3 of the textbook: Computer Security: Principles and Practice” by & , , 2015 [Pub key Encryption concept]
Optional deeper reading for interested students:
• Sections 8.1.1, 8.1.2 and 8.2.1 of the textbook: Introduction to Modern Cryptography, by and , Chapman & Hall/CRC, 2014.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com