3. Cryptography 2 – RSA and DH
Cryptography 2:
RSA and DH
Alvaro Monsalve
CITS3004
1
1. Symmetric Cipher Problems
2. Asymmetric Ciphers
2.1. RSA
2.2. DH
3. Hashing
4. Symmetric vs Asymmetric Ciphers
5. Blockchain
Agenda
2
• DES, AES are all symmetric key cryptosystem
– i.e., using 1 key to encrypt and decrypt
• In a network, we have many more than 2 users
– Given n users, how many different keys do we need to
establish connected between every pair of users?
3
1. Problems of symmetric
key cryptosystem
Need to generate O(n2) number of
keys and manage them.
• In a public key cryptography system, two different keys
are used – one publicly available and one secret.
• Others who wish to communicate with you can use your
public key to encrypt their messages.
• Only you can decrypt to reveal the message using your
private key.
• You only need to provide 1 key to communicate with
anyone!
4
Public Key Cryptography
5
Public Key Crypto
Sender Receiver
Encryption
algorithm
Decryption
algorithm
plaintext ciphertext plaintext
Bob’s public key Bob’s private key
fdafieoa
jfvhlfjea
asymmetric key cipher
Normal usage
6
Public Key Crypto
Sender Receiver
Encryption
algorithm
Decryption
algorithm
plaintext ciphertext plaintext
Alice’s private key Alice’s public key
Geiafea
vhieslfe
asymmetric key cipher
Personal
message
Personal
message
Validating your identity
• Given two large primes
p and q
• Compute n = p x q
• Given n, how to get p
and q?
7
2. Asymmetric key ciphers
Asymmetric key
encryption
Integer
Factorisation
Problem
RSA
Rabin
Discrete logarithm
problem
ElGamal
ECC
… …
Given Produce Difficulty
Integers: p, q, r, s, t Product: N Polynomial
Integer: N Factorise: p, q, r, s, t Non Polynomial
8
Integer Factorisation
Primes p, q N = p*q
Easy
Hard
Use this fact to construct RSA-type public key cryptosystems
• Q: 11x mod 13 = 9, what is x?
– 111 mod 13 = 11
– 112 mod 13 = 4
– 113 mod 13 = 5
– 114 mod 13 = 3
– 115 mod 13 = 7
– 116 mod 13 = 12
– 117 mod 13 = 2
– 118 mod 13 = 9
9
Integer Factorisation
How difficult is it when
p is 512 bits?
• First public key cryptosystem
• World wide standard for the last 30 years
• RSA named after its creators
– Ron Rivest, Adi Shamir and Leonard Adleman
10
2.1. RSA
• Prime number
• GCD (greatest common divisor)
• Euclidean Algorithm
• Relatively prime
• Congruence
• Multiplicative inverse
11
Prerequisite for RSA
It is a number that is only divisible by 1 and itself
without any remainders
12
Prime number
45 = 32 x 5 18 = 21 x 32
GCD(45, 18) = 20 x 32 x 50 = 9
GCD is the largest whole number that can divide both a
and b without a remainder
13
Greatest Common Divisor
• Given gcd(a, b) = d
– a = b*q + r (b is smaller than a)
– gcd(a, b) ≡ gcd(b, r) = d
• What is the GCD of 33 and 18?
14
Euclidean Algorithm
• Next step, find x and y such that a*x + b*y = d
• We use this later to calculate the multiplicative inverse
• Example
– a = 204, b = 72, find 204x + 72y = d. First, calculate d
– 204 = 72 * 2 + 60
– 72 = 60 * 1 + 12
– 60 = 12 * 5 + 0
– Therefore, gcd(204, 72) = 12 (the last integer with remainder 0)
15
Extended Euclidean
Algorithm
• gcd(204, 72) = 12, now reverse calculate
• 12 = 72 – 60 * 1
• 12 = 72 – (204 – 72 * 2) * 1 collect terms together
• 12 = 72 * 3 – 204 * 1
• 12 = 204 * (-1) + 72 * (3)
• Hence, x = -1, y = 3
16
Extended Euclidean
Algorithm
• Lets try one more -> GCD(89, 64)
∴ GCD(89, 64) = 1
17
Extended Euclidean
Algorithm
89 = 64*1 + 25
25 = 14*1 + 11
11 = 3*3 + 2
2 = 1*2 + 0
64 = 25*2 + 14
14 = 11*1 + 3
3 = 2*1 + 1
• Now, trace back:
1 = 3 – 2*1
1 = 3 – (11 – 3*3) = 3*4 – 11
1 = (14 – 11*1)*4 – 11 = 14*4 – 11*5
1 = 14*4 – (25 – 14*1)*5 = 14*9 – 25*5
1 = (64 – 25*2)*9 – 25*5 = 64*9 – 25*23
1 = 64*9 – (89 – 64*1)*23 = 64*32 – 89*23
∴ 1 = 64*32 + 89*(-23)
18
Extended Euclidean
Algorithm
89 = 64*1 + 25
25 = 14*1 + 11
11 = 3*3 + 2
64 = 25*2 + 14
14 = 11*1 + 3
3 = 2*1 + 1
∴ GCD(89, 64) = 1
collect terms together
Two numbers a and b are relatively prime, if they have
no common divisors > 1.
a = 8 divisors 1, 2, 4, 8
b = 15 divisors 1, 3, 5, 15
8 and 15 are relatively prime
19
Relatively Prime
In modular arithmetic, congruence is
– Having the same remainder when divided by a specific
integer
– Given n > 0, two integers a and b are congruent modulo n
– a ≡ b mod n
• E.g., 10 ≡ 1 mod 3 -> 10 and 1 are congruent modulo 3
• E.g., 12 ≡ 2 mod 5 -> 12 and 2 are congruent modulo 5
20
Congruence
Find x and y such that x*y ≡ 1 mod n
• If n = 10
21
Multiplicative Inverse
1 x 1 = 1 2 x 1 = 2 3 x 1 = 3 9 x 1 = 9
1 x 2 = 2 2 x 2 = 4 3 x 2 = 6 9 x 2 = 8
1 x 3 = 3 2 x 3 = 6 3 x 3 = 9 9 x 3 = 7
1 x 4 = 4 2 x 4 = 8 3 x 4 = 2 9 x 4 = 6
1 x 5 = 5 2 x 5 = 0 3 x 5 = 5 . . . 9 x 5 = 5
1 x 6 = 6 2 x 6 = 2 3 x 6 = 8 9 x 6 = 4
1 x 7 = 7 2 x 7 = 4 3 x 7 = 1 9 x 7 = 3
1 x 8 = 8 2 x 8 = 6 3 x 8 = 4 9 x 8 = 2
1 x 9 = 9 2 x 9 = 8 3 x 9 = 7 9 x 9 = 1
For example, gcd(60, 37) = 1
• What is the multiplicative inverse of 37 mod 60?
– What is x when 37 * x = 1 mod 60?
• Use the Extended Euclidean Algorithm
• 1 = 37*13+60*(-8)
• x = 13
22
Multiplicative Inverse
Calculate x
23
RSA: Encryption Decryption
Sender Receiver
RSA encryption
C = PE mod N
RSA decryption
P = CD mod N
Cipher-
text C
Bob’s Public Key
(E, N)
Bob’s Private key
(D, N)
Plaintext
P
Plaintext
P
Q: How to create those keys?
1. Select two large (> 1024 bits) primes p, q
2. Compute modulus n = p*q and
3. Compute ϕ(n) = (p-1)*(q-1)
• ϕ is Euler’s Totient Function
4. Pick an integer e relatively prime to ϕ(n)
• gcd(e, ϕ(n)) = 1; 1 < e < ϕ(n) 5. Compute d such that e*d = 1 mod ϕ(n) • Public key (e, n) • Private key (d, n) 24 RSA: Key Generation Key Generation 1. p = 5, q = 11 2. n = pq = 55 3. ϕ(n) = (p-1)*(q-1) = 4 * 10 = 40 4. e = 13 (gcd(40, 13) = 1) • e = {3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39} 5. Compute d, e*d = 1 mod ϕ(n), 13*d = 1 mod 40, d = 37 25 RSA example Public Key = {e, n} = {13, 55} Private Key = {d, n} = {37, 55} • Bob wants to send Alice a secret message: 13 08 16 • Bob uses Alice’s public key to calculate the following – 1313 mod 55 = 08 – 0813 mod 55 = 28 – 1613 mod 55 = 26 • Bob sends 08 28 26 26 RSA example Public Key = {e, n} = {13, 55} Private Key = {d, n} = {37, 55} • Alice receives 08 28 26 • Alice uses her private key, d = 37, to decrypt message • 0837 mod 55 = 13 • 2837 mod 55 = 08 • 2637 mod 55 = 16 27 RSA example Public Key = {e, n} = {13, 55} Private Key = {d, n} = {37, 55} 2637 mod 55 = 26 x 2636 mod 55 = 26 x 67618 mod 55 = 26 x 1618 mod 55 = 26 x 2569 mod 55 = 26 x 369 mod 55 = 26 x 36 x 314 mod 55 = 314 mod 55 = 16 This is 1! • Unfortunately, no. • RSA requires many computations to carry out – Mostly the power computation 1. Use modular operations to reduce intermediate results • [(a mod n) × (b mod n)] mod n = (a × b) mod n 2. Use fast exponent computational algorithms • See MATH1721 – Mathematics Foundations 28 Is RSA quick? • https://en.wikipedia.org/wiki/RSA_Factoring_Challenge • Different length of subprime numbers • Challenges are no longer valid – ended in 2007 • RSA-768 is the largest subprime solved to date (2009) • Remember, RSA uses p and q both 1024 bits as basic mode, up to 2048 bits 29 RSA Challenge https://en.wikipedia.org/wiki/RSA_Factoring_Challenge • Given g, x and a large prime p • Compute y = gx mod p • Given y, how to get x? 30 Asymmetric key ciphers Asymmetric key encryption Integer Factorisation Problem RSA Rabin Discrete logarithm problem ElGamal ECC … … • Given g, y and prime p, find an integer x, if any, such that y = gx mod p • Used to construct Diffie-Hellman and ElGamal-type public cryptosystems – DH, DSA (Digital Signature Algorithm) etc. 31 Discrete Logarithm problem g, x, p y = gx mod p Easy Hard x g, y, p • Diffie-Hellman is a public key distribution scheme • Proposed by Whitfield Diffie and Martin Hellman in 1976 • Many applications, just to name a few… 32 2.2. DH Key Exchange TCP/IP Model OSI Model Protocols Application Application DNS, DHCP, FTP, HTTPS, SSH etc. Presentation JPEG, MIDI, MPEG, TIFF etc. Session NetBIOS, NFS, PAP, SQL, ZIP etc. Transport Transport TCP, UDP, SSL/TLS etc. Internet Network ICMP, IGMP, IPSec, IPv6 RIP etc. Link Data Link ARP, ATM, FDDI, PPP, STP, HDLC etc. Physical Bluetooth, Ethernet, DSL, Wi-Fi etc. • Users can exchange a secret key • Requires no prior secrets, can be established in real time over untrusted network • Based on discrete logarithms of large numbers • Required numbers are: – p: one prime – g: a primitive root of p (or a base) – x: a secret key 33 DH key agreement protocol y = gx mod p 34 DH process Sender Receiver Pick a random number a Pick a random number b Choose p, a large prime, and g (g < p) Send ga mod p Send gb mod p Compute k k = (gb)a = gab mod p Compute k k = (ga)b = gab mod p • p and g are both publicly available numbers – p is at least 512 bits • Users pick private values a and b • A common key k is used • Attacker has ga, gb, p, g – Has to compute gab from the above information – Discrete Logarithm Problem! 35 DH process • Alice and Bob choose public numbers – p = 17 – g = 6 • Alice picks a = 5, Bob picks b = 3. – ga mod 17 = 65 mod 17 = 7 – gb mod 17 = 63 mod 17 = 12 • Alice and Bob computes k = gab – k = gab mod 17 = (65)3 mod 17 = (63)5 mod 17 = 3 • Alice and Bob now use 3 for the symmetric cipher! 36 DH Example Man In The Middle attack (MITM) 37 DH MITM attack Sender Receiver Send ga mod p Send gb mod p Send ga mod p Send gc mod p Send gb mod p Send gc mod p Compute k1 k1 = (gc)a = gac mod p Compute k2 k2 = (gc)b = gbc mod p Compute k1 and k2 k1 = (ga)c = gac mod p k2 = (gb)c = gbc mod p • Attacker can exploit DH with MITM attack • The problem is the lack of authentication • To prevent MITM, use authentication – E.g., using signatures – ISO/IEC 9796 (9796-2:2010 is the current version) 38 DH MITM attack 39 DH MITM mitigation Sender Receiver A, ga B, gb, SIGB(ga, gb, A) SIGA(gb, ga, B) Include the identify in the signature to thwart identity misuse attacks (e.g., MITM) 40 DH MITM mitigation Sender Receiver A, ga E, ge, SIGE(ga, ge, A) Cannot validate the identify using Bob’s public key Even cannot forge Bob’s public key without knowing Bob’s private key. We assume Bob’s public key is known to Alice. • DH can be used more than 2 users at a time – E.g., 3 users 41 DH with 2+ Users Alice Bob (1) ga Chuck (1) gc (1) gb (2) gac (2) gab(2) gbc k = gabc mod p RSA – Can be used for message encryption decryption – Can provide authentication – Allow anyone to communicate with me DH – Only exchange shared key, typically for symmetric ciphers – Requires authentication to thwart attacks – Already identified who I want to communicate with 42 RSA vs DH • Also known as – Hash functions, message digest, one-way transformation etc. • Generate a message of fixed length given an arbitrary length of the message – Typically 128 or 160 bits • Examples include – MD5 (message digest) – 128 bits output – SHA-2 (secure hashing algorithm) 256/224, 512/384 bits 43 3. Hashing • The primary goal/application is to generate and verify digital signature 44 Hashing Hash H Sign Message m Signature Sig(H(m)) H(m) Private key Hash H Verify Message m Check m and signature H(m) Public keySignature Sig(H(m)) Send Receive Send m and signature • Password hashing – Do not store the raw password – Store H(password + salt) and salt – Salt makes dictionary attack more difficult • Message integrity using message authentication code (MAC) – Agree on a secret key k – Compute H(m|k) and send with m – Does not require encryption algorithm • File integrity (cyber forensics) • Generating random number 45 Applications of Hashing • Let us use RSA to sign the message • Alice first gets the hash of the message h(m) • Then sign using her private key d such that – s = (h(m))d mod n • Alice sends the encrypted message and the signature to Bob • The receiver, Bob, can check the authenticity of the message by comparing the message m and se mod n 46 Signing using RSA d is Alice’s private key e is Alice’s public key • Message m is {06, 14, 11}, C is {51, 49, 11} • Hash function H(m) = ∑(3mi + 1) mod 11 • Then, our hash value is: 19+43+34 mod 11 ≡ 8 • Sign the Hash: s = 827 mod 55 = 2 • Alice sends C and s: ({51, 49, 11}, 2) • Bob can decrypt the message, calculate hash of the message, and decrypt the sign using Alice’s public key to check the authenticity • H(m) = 23 mod 55 = 8 • If the original message is changed (or the hash), then they will not match. 47 Signing using RSA Public Key = {e, n} = {3, 55} Private Key = {d, n} = {27, 55} Using the RSA example 2 Symmetric Asymmetric Key type Shared secret Public and Private Key pair Algorithm Classified or Open Open Key distribution Required Not required Strengths • Fast • Easy to use • Provides authenticity of the source • Private key is kept secret Weaknesses • Shared secret • No authenticity • Public key management • Slow Examples AES, 3DES RSA, DH 48 4. Symmetric vs Asymmetric • Key distribution by Public key cipher – E.g., RSA, DH, ECDH-RSA • Data encryption by symmetric key cipher – E.g., AES • Most security protocols use this approach 49 Best of the both • What is blockchain? – A distributed ledger technology to connect different untrusted parties over the internet and store data securely from tampering – Uses chained hash blocks for authenticity – Core technology for cryptocurrency • E.g., Bitcoin, Ethereum etc. – Blockchain allows different untrusted people to agree on the state of the system – The history blocks (of transactions) are stored in distributed storage nodes -> Decentralisation!
50
5. Blockchain
• Why distributed system?
– A single point of failure
– Authority power
– Trust issues
51
Blockchain
52
Blockchain
Alice
Bob
Chuck
David
Eve
Traditionally, we have a single entity
(e.g., Bank) to keep track of the
transactions
Bank Sender Recipient Amount
David Chuck $30
Alice Eve $20
53
Blockchain
Alice
Bob
Chuck
David
Eve
In Blockchain,
everyone keeps the
record of transactions
Sender Recipient Amount
David Chuck $30
Alice Eve $20
Sender Recipient Amount
David Chuck $30
Alice Eve $20
Sender Recipient Amount
David Chuck $30
Alice Eve $20
Sender Recipient Amount
David Chuck $30
Alice Eve $20
Sender Recipient Amount
David Chuck $30
Alice Eve $20
If an error occurs in
one record, it can be
checked against others
for validation.
• When a transaction happens, everyone in the
network records the transaction
• Each node records a list of transactions – called Block
• The next block is chained from the previous block
hash
54
Blockchain – details
55
Blockchain – details
Transaction 1
Transaction 2
Transaction 3
…
Transaction n
Block 1
Hash of Block 1: xxxxxxxxxx….
56
Blockchain – details
• To calculate the hash value
of the block, Merkle tree is
used.
• Merkle tree is simply a tree
of hashed values of each
transaction computed
bottom up
• Merkle tree allows you to:
– Summarise all the transactions with a digital fingerprint
– Quick/simple test to verify a transaction is included or not
– Each branch can be downloaded on its own for verification
– Provide integrity and validity of data
• What do you do if you have a odd number of
transactions?
– Repeat the last hash value twice
57
Blockchain – details
58
Blockchain – details
Transaction 1
Transaction 2
Transaction 3
…
Transaction n
Block 1 hash
Transaction 1
Transaction 2
Transaction 3
…
Transaction n
Block 2 hash
Transaction 1
Transaction 2
Transaction 3
…
Transaction n
Block n-1 hash
Transaction 1
Transaction 2
Transaction 3
…
Transaction n
Block 1 Block 2 Block 3 Block n
. . .
• Blockchain is just a sequence of hash-chained
records
– These records are immutable, stored in distribution
• When a transaction occurs, the transaction is
recorded to peer blocks (can be an arbitrary number)
using the hash-chain
– That is, you cannot modify the transaction
59
Blockchain – details
60
Blockchain – details
Transaction 1
Transaction 2
Transaction 3
…
Transaction n
Block 1 hash
Transaction 1
Transaction 2
Transaction 3
…
Transaction n
Block 2 hash
Transaction 1
Transaction 2
Transaction 3
…
Transaction n
Block n-1 hash
Transaction 1
Transaction 2
Transaction 3
…
Transaction n
Block 1 Block 2 Block 3 Block n
. . .
Altered record
Altered hash! Altered hash!
All nodes have the same blockchain, so you can easily
find the error
Block 2 hash
Transaction 1
Transaction 2
Transaction 3
…
Transaction n
Block n-1 hash
Transaction 1
Transaction 2
Transaction 3
…
Transaction n
• Underlying technology for Cryptocurrency
– E.g. a Bitcoin wallet address:
3NT1wrYVYYsPorK1jq9UVLVbzbroSYUaP7
• Addresses are used only ONCE – why?
– Due to its properties described previously
– Satoshi Nakamoto created Bitcoin, and also proposing
Blockchain (used to be Block ‘space’ chain)
• Satoshi Nakamoto is an unknown identify
61
Using Blockchain
Bitcoin white paper: https://bitcoin.org/bitcoin.pdf
https://bitcoin.org/bitcoin.pdf
• Cryptocurrency is generated through mining
– This is the only way to release new cryptocurrency
– E.g. we have 18.5M bitcoins in circulation as in Aug 2020*
• Mining is done by validating the block
– i.e. calculating that hash value for the next block
• To earn cryptocurrency, you have to be the first one to
mine the block, as well as be part of the longest link
– I will show you what it means soon
62
Cryptocurrency
*https://www.buybitcoinworldwide.com/how-many-bitcoins-are-there
https://www.buybitcoinworldwide.com/how-many-bitcoins-are-there
• Using Blockchain for cryptocurrency has some
important issues that needs to be manages
– What could go wrong?
• Double spend attack
• Majority malicious nodes
– The big concern is the consensus problem
63
Cryptocurrency
64
Cryptocurrency
Alice
Bob
Chuck
David
Eve
Send $10
Send $10
But Even only has $10!
• When a transaction happens, all the nodes will vote.
• The transaction that has the majority of votes will be
recorded in the Blockchain
65
Cryptocurrency
66
Cryptocurrency
Alice
Bob
Chuck
David
Eve
Send $10
Send $10
Vote for transaction
67
Cryptocurrency
Alice
Bob
Chuck
David
Eve
Send $10
Send $10
Cannot trust every
node in the network!
This is a Sybil attack
Eve”
Eve”
• To overcome this problem, evidence is provided to
cast a vote
– Named Proof-of-Work
• Each node will perform some brute force task, which
spends resources
– What is the brute force task?
• E.g., Certain property of the hash value to be produced
68
Cryptocurrency
• Brute force task example:
– Given a hash function f(m) = 31 * m * c + c + 7 mod 79
– Given message m = 29
– Find a nonce value c such that f(m) is a single digit
69
Cryptocurrency
c = 1 -> f(m) = 37
c = 2 -> f(m) = 67
c = 3 -> f(m) = 18
…
c = 13 -> f(m) = 2
70
Cryptocurrency
Alice
Bob
Chuck
David
Eve
Send $10
Send $10
Eve only has one computer
to perform 3 Brute force
tasks in order to vote!
Eve”
Eve”
• What happens to the invalid votes? Or different
votes at the same time?
• This scenario is called forks
71
Cryptocurrency
Existing
transactions
Transactions A
Transactions B
Transactions C Transactions D
This transaction is still in the
block, but not mined any more
72
Cryptocurrency
Alice
Bob
Chuck
David
Eve
Send $10
Send $10
If Eve can afford > 51% of the
network nodes (or equivalent
computing resources), Eve
can successfully manipulate
transactions
Eve”
Eve”
• And there are other issues we need to consider
1. Forks that can be caused by sybil nodes or selfish mining
2. Selfish mining: miners trying to increase their rewards by
keeping blocks private
3. DNS attacks: sending peers wrong information
4. Mempool attacks: flooding new blocks with transactions
5. DDoS attacks: achieving denial of service
6. Consensus delay: preventing peers from reaching consensus
7. Theft of wallets – probably one of the biggest issues now
73
Cryptocurrency
• Smart contracts
• Crowdfunding
• Governance
• Auditing
• File Storage
• Intellectual Property
• IoT
• Identity management
• Anti-money laundering
• Etc…
74
Other uses of Blockchain
https://blockgeeks.com/guides/what-is-blockchain-technology/
• Introduction to RSA and DH and their details
• Hashing
• Symmetric vs Asymmetric ciphers
• Blockchain overview
75
Summary
• DH C code
– https://www.geeksforgeeks.org/implementation-diffie-hellman-algorithm/
• RSA and ECC tutorial
– https://www.tutorialspoint.com/cryptography/public_key_encryption.htm
• RSA in more details
– https://blog.sigmaprime.io/introduction-to-rsa.html
• Basics of ECC
– https://dl.acm.org/citation.cfm?id=3064818
• Blockchain resources
– Demo online: https://anders.com/blockchain/
– Other video/resource from MIT: http://blockchain.mit.edu/
– Bitcoin developer reference: https://bitcoin.org/en/developer-reference
– Mining: https://www.investopedia.com/tech/how-does-bitcoin-mining-work/
76
Additional Items
https://www.geeksforgeeks.org/implementation-diffie-hellman-algorithm/
https://www.tutorialspoint.com/cryptography/public_key_encryption.htm
https://blog.sigmaprime.io/introduction-to-rsa.html
https://dl.acm.org/citation.cfm?id=3064818
https://anders.com/blockchain/
http://blockchain.mit.edu/
https://bitcoin.org/en/developer-reference
https://www.investopedia.com/tech/how-does-bitcoin-mining-work/