Cryptography and Symmetric Keys in Digital Communication
Digital Signatures
Campbell R. Harvey
Duke University and NBER
January 19, 2018
Innovation and Cryptoventures
Definition
Cryptography is the science of communication in the presence of an
adversary. Part of the field of cryptology.
2
Campbell R. Harvey 2018
Goals of Adversary
•
Alice sends message to Bob
•
Eve is the adversary
3
Campbell R. Harvey 2018
Goals of Adversary
Eve’s goals could be:
1.
Eavesdrop
2.
Steal secret key so that all future messages can be intercepted
3.
Change Alice’s message to Bob
4.
Masquerade as Alice in communicating to Bob
4
Campbell R. Harvey 2018
Symmetric Keys
Early algorithms were based on symmetric keys.
•
This meant a common key encrypted and decrypted the message
•
You needed to share the common key and this proved difficult
5
Campbell R. Harvey 2018
Symmetric Keys
•
Early methods relied on a shared key or code
•
A message would be encrypted and sent but the receiver needed to
decode with a key or a special machine
•
Example: The “Lektor” in James Bond,
From Russia with Love
.
6
Campbell R. Harvey 2018
Symmetric Keys
•
However, you needed to securely share the key or decoder.
7
Campbell R. Harvey 2018
Symmetric Keys
•
However, you needed to securely share the key or decoder.
8
The “adversary”
Campbell R. Harvey 2018
Symmetric Keys
•
Nazi Enigma Machine is an earlier version of the “Lektor”
9
https://www.youtube.com/watch?v=G2_Q9FoD-oQ
https://www.youtube.com/watch?v=V4V2bpZlqx8
Recommended videos!
Campbell R. Harvey 2018
Secret Keys
Symmetric key
•
DES (Data Encryption Standard)
was a popular symmetric key
method, initially used in SET (first
on-line credit card protocol)
•
DES has been replaced by AES
(Advanced Encryption Standard)
10
Campbell R. Harvey 2018
Diffee-Hellman Key Exchange
•
Breakthrough in 1976 with Diffie-Hellman-Merkle key exchange
•
There is public information that everyone can see. Each person, say Alice and
Bob, have secret information.
•
The public and secret information is combined in a way to reveal a single
secret key that only they know
11
https://www.youtube.com/watch?v=YEBfamv-_do
Campbell R. Harvey 2018
Diffee-Hellman Key Exchange
•
Will use prime numbers and modulo arithmetic
•
We already encountered one example of modular arithmetic in the SHA-256
which uses mod=2
32
or 4,294,967,296
12
https://www.youtube.com/watch?v=YEBfamv-_do
Campbell R. Harvey 2018
Key Exchange
Numerical example
•
“5 mod 2” = 1
•
Divide 5 by 2 the maximum number of times (2)
•
2 is the modulus
•
The
remainder
is 1
•
Remainders never larger than (mod-1) so for mod 12 (clock) you would
never see remainders greater than 11.
•
EXCEL function
= mod(number, divisor) e.g., mod(329, 17) = 6
13
“mod”
Campbell R. Harvey 2018
Key Exchange
Alice and Bob decide on two public pieces for information
•
A modulus (say 17)
•
A generator (or the base for an exponent) (say 3)
•
Alice has a
private key
(
15
)
•
Bob has a
private key
(
13
)
•
Is it possible for them to share a common secret that is unlikely to be
intercepted?
14
https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/diffie-hellman-key-exchange-part-2
Campbell R. Harvey 2018
Key Exchange
Alice:
Calculates 3
15
mod 17 = 6 (i.e.,
=mod(3^(
15
), 17)
)
•
Alice send the message “6” to Bob
15
Campbell R. Harvey 2018
Key Exchange
Alice:
Calculates 3
15
mod 17 = 6 (i.e.,
=mod(3^(
15
), 17)
)
•
Alice send the message “6” to Bob
•
Eve intercepts the message!
16
Campbell R. Harvey 2018
Key Exchange
Bob:
Calculates 3
13
mod 17 = 12 (i.e.,
=mod(3^(
13
), 17)
)
•
Bob send the message “12” to Alice
17
Campbell R. Harvey 2018
Key Exchange
Bob:
Calculates 3
13
mod 17 = 12 (i.e.,
=mod(3^(
13
), 17)
)
•
Bob send the message “12” to Alice
•
Eve intercepts the message! Now Eve has the 6 and the 12.
18
Campbell R. Harvey 2018
Key Exchange
Alice:
Takes Bob’s message of 12 and raises it to the power of her private key.
Calculates
12
15
mod 17 =
10
(i.e.,
=mod(12^(
15
), 17)
)
*
•
This is their common secret
19
*EXCEL only does 15 digits so this will not work
Campbell R. Harvey 2018
Key Exchange
Bob:
Takes Alice’s message of
6
and raises it to the power of his private key.
Calculates
6
13
mod 17 =
10
(i.e.,
=mod(6^(
13
), 17)
)
•
This is their common secret
20
Campbell R. Harvey 2018
Key Exchange
Eve
She has intercepted their message.
However, without the common secret
key, there is little chance she can recover the shared secret.
21
Campbell R. Harvey 2018
Key Exchange
Common secret
•
Alice can now encrypt a message with the common secret and Bob can
decrypt it with the common secret.
•
Notice this is a common secret.
•
Next we will talk private/public keys. That is, both and Alice have separate
public keys and separate private keys.
22
Campbell R. Harvey 2018
Key Exchange (Optional slide)
Why does this work
They are solving the same problem.
•
Alice sent Bob 3
15
mod 17 = 6.
•
Bob raises the to power of
13
.
This is the same as
6
13
mod 17 = [3
15
]
^(
13
)
mod 17 =10
23
Alice’s original calculation
Campbell R. Harvey 2018
Key Exchange (Optional slide)
Why does this work
They are solving the same problem.
•
Bob sent Alice 3
13
mod 17 = 12.
•
Alice raises the to power of
15
.
This is the same as
12
15
mod 17 = [3
13
]
^(
15
)
mod 17 =10
24
Bob’s original calculation
Campbell R. Harvey 2018
Key Exchange (Optional slide)
Why does this work
They are solving the same problem. The modular arithmetic is crucial.
•
See!
[3
13
]
^(
15
)
= [3
15
]
^(
13
)
25
Campbell R. Harvey 2018
Key Exchange
RSA and ECC
•
Now we will introduce key pairs.
•
The basic idea of modular arithmetic
provides the foundation for RSA
private/public key cryptography.
•
The prime numbers that are used are huge. Private keys are
mathematically linked to public keys.
26
Campbell R. Harvey 2018
RSA: High Level Overview
See my
Cryptography 101
deck for much more detail.
•
Two prime numbers are chosen and they are secret (say 7 and 13, called
p, q
).
•
Multiply them together. The product (
N
=91) is public but people don’t know
the prime numbers used to get it.
•
A public key is chosen (say 5).
•
Given the two prime numbers, 7 and 13, and the public key, we can deri
ve the
private key, which is 29.
27
Campbell R. Harvey 2018
RSA
Issues with RSA
•
RSA relies on factoring
•
N is public (our example was 91)
•
If you can guess the factors, p, q, then you can discover the private key
28
Campbell R. Harvey 2018
RSA
Issues with RSA
•
Factoring algorithms have become very efficient
•
To make things worse, the algorithms become more efficient as the size of
the N increases
•
Hence, larger and larger numbers are needed for N
•
This creates issues for mobile and low power devices that lack the
computational power
29
http://www.slate.com/articles/health_and_science/science/2016/01/the_world_s_largest_prime_number_has_22_338_618_digits_here_s_why_you_should.html
Campbell R. Harvey 2018
Elliptic Curve Cryptography
Mathematics of elliptic curves
•
Does not rely on factoring
•
Curve takes the form of
y
2
= x
3
+ ax + b
30
Note: 4a
3
+ 27b
2
≠ 0
Campbell R. Harvey 2018
Bitcoin uses a=0 and b=7
Note that diagram is “continuous” but we
will be using discrete versions of this arithmetic
Elliptic Curve Cryptography
Properties
•
Symmetric in x-axis
•
Any non-vertical line intersects in three points
•
Algebraic representation
31
Campbell R. Harvey 2018
Elliptic Curve Cryptography
Properties: Addition
32
P
Q
R
P+Q
Denote Elliptic Curve
as E
Campbell R. Harvey 2018
Elliptic Curve Cryptography
Properties: Doubling
33
P
2P
Denote Elliptic Curve
as E
Campbell R. Harvey 2018
Elliptic Curve Cryptography (Optional slide)
Properties: Other
34
(a)
P + O = O + P = P for all P
∈
E.
(existence of identity)
(b) P + (−P) = O for all P
∈
E.
(existence of inverse)
(c) P + (Q + R) = (P + Q) + R for all P, Q, R
∈
E.
(associative)
(d) P + Q = Q + P for all P, Q
∈
E
(communativity)
Denote Elliptic Curve
as E
Campbell R. Harvey 2018
Elliptic Curve Cryptography (Optional slide)
Why use in cryptography?
•
Suggested by Koblitz and Miller in 1985
•
Implemented in 2005
•
Key insight:
•
Adding and doubling on the elliptic curve is easy but undoing the adding is very difficult
35
Campbell R. Harvey 2018
Elliptic Curve Cryptography (Optional slide)
Modulo arithmetic on EC
•
Example of modulo 67 (means only
points are between 0 and 66
•
Notice the symmetry
36
Campbell R. Harvey 2018
http://www.coindesk.com/math-behind-bitcoin/#
Elliptic Curve Cryptography (Optional slide)
Modulo arithmetic on EC
•
Notice the symmetry (reflection in
the red line)
37
Campbell R. Harvey 2018
http://www.coindesk.com/math-behind-bitcoin/#
Elliptic Curve Cryptography (Optional slide)
Modulo arithmetic on EC
•
Example of modulo 67
•
Addition of (2,22) and (6,25)
•
Note (2,22) called the “base point”
•
The dashed blue line wraps around
and intersects at (47,39) and the
reflection is (47,28)
38
Campbell R. Harvey 2018
http://www.coindesk.com/math-behind-bitcoin/#
Elliptic Curve Cryptography (Optional slide)
Modulo arithmetic on EC
•
Example of modulo 67
•
Addition of (2,22) and (6,25)
•
Note (2,22) called the “base point”
•
The dashed blue line wraps around
and intersects at (47,39) and the
reflection is (47,28)
39
Campbell R. Harvey 2018
http://www.coindesk.com/math-behind-bitcoin/#
Elliptic Curve Cryptography (Optional slide)
Four choices:
•
Form of elliptic curve
•
Prime modulo
•
Base point
•
Order
40
Campbell R. Harvey 2018
http://www.coindesk.com/math-behind-bitcoin/#
Elliptic Curve Cryptography (Optional slide)
Four choices:
•
Form of elliptic curve
: y
2
= x
3
+ 7
•
Prime modulo
: 2
256
– 2
32
– 2
9
– 2
8
– 2
7
– 2
6
– 2
4
- 1 = FFFFFFFF FFFFFFFF
FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
•
Base point
: 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB
2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8
FD17B448 A6855419 9C47D08F FB10D4B8
•
Order
: FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B
BFD25E8C D0364141
41
Campbell R. Harvey 2018
http://www.coindesk.com/math-behind-bitcoin/#
Elliptic Curve Cryptography (Optional slide)
How it works:
•
Private key is a random number chosen between 1 and the order
•
Public key = private key*base point
•
Maximum number of private keys (and bitcoin addresses) is equal to the
order.
•
It is straightforward to go from private key to a public key – but brutally
difficult to go from public key to private key.
42
Campbell R. Harvey 2018
http://www.coindesk.com/math-behind-bitcoin/#
Elliptic Curve Cryptography (Optional slide)
How it works:
1. Choose private key and derive public key
•
Let prime modulus = m
•
Let base point (x,y) = G
•
Let order = n
•
Let private key =
d
(which is just a number)
Public key Q(x,y) =
d
*G [operations on the elliptic curve with prime modulus m]
43
Campbell R. Harvey 2018
http://www.coindesk.com/math-behind-bitcoin/#
Elliptic Curve Cryptography (Optional slide)
How it works:
2. Sign
•
Let data = z (which could be a SHA-256 of the data you are signing)
•
Generate a random number k
•
Calculate k*G which leads to particular coordinates (x,y)
*
•
Calculate r = x mod n [Note n=order]
•
Calculate s = (z + r*
d
)/k mod n
Digital Signature (DS) = (r, s) is just a set of coordinates
44
Campbell R. Harvey 2018
http://www.coindesk.com/math-behind-bitcoin/#
*I am not sure what modulus is used for this EC operation.
Private key
Elliptic Curve Cryptography (Optional slide)
How it works:
3. Verify
•
Calculate w = s
-1
mod n
•
Calculate u = z*w mod n
•
Calculate v = r*w mod n
•
Calculate the point (
x’
, y’) = uG + vQ
•
Verify that
r
=
x’
mod n If yes, verified.
Remember DS = (
r
, s)
45
Campbell R. Harvey 2018
http://www.coindesk.com/math-behind-bitcoin/#
Public key
Base point
Elliptic Curve Cryptography (Optional slide)
How it works:
4. Intuition
•
Anyone can encrypt something with a public key
•
The digital signature algorithm uses the data, a random number, and
both
the private and public keys
•
Verification shows that only the owner of both the private and public key
could have signed. Verification is a “yes” or a “no”.
46
Campbell R. Harvey 2018
http://www.coindesk.com/math-behind-bitcoin/#
ECDSA
•
Private key is a number called “signing key” (SK). It is secret.
•
Public key is the “verification key” and is
mathematically linked
to
the private key
47
Campbell R. Harvey 2018
SK
EC
VK
Private key:
(number)
Elliptic curve operations:
Need base point, modulus, order
Public key:
coordinate (x, y)
Note: Easy to generate a public key with a private key. Not easy to go the other way.
ECDSA
•
Digital signature
48
Campbell R. Harvey 2018
SK
EC
DS
Private key:
(number)
Elliptic curve operations:
Need base point, modulus, order (n)
Digital signature:
coordinate (r, s)
Message
Nonce
Nonce:
(random number)
ECDSA
•
Verification
49
Campbell R. Harvey 2018
VK
EC
(x’, y’)
Public key:
(x, y)
Elliptic curve operations:
Need base point, order (n)
Derive new point
on elliptic curve
Message
r
DS
coordinates
s
r = x’ mod n ?
Yes
(verified)
No
(rejected)
Check x coordinate
of new point and DS
How DSAs Work
Notice
•
Proves that the person with the private key (that generated the
public key) signed the message.
•
Interestingly, digital signature is different from a usual signature in
that
it depends on the message
, i.e., the signature is different for
each different message.
•
In practice, we do not sign the message, we sign a cryptographic
hash of the message. This means that the size of the input is the
same no matter how long the message is.
50
Campbell R. Harvey 2018
ECDSA in Action
51
Campbell R. Harvey 2018
https://kjur.github.io/jsrsasign/sample-ecdsa.html
ECDSA in Action
52
Campbell R. Harvey 2018
OP_CHECKSIG uses Public Key + Digital Signature + Hash of Transaction
Verifies whether this transaction has been signed by the owner of the Private Key
Application: PGP Email
My public key for secure
•
You can encrypt an email
to me with my public key
and only I can decrypt
with my private key.
53
Campbell R. Harvey 2018
Application: PGP Email
Steps
1.
Message compressed
2.
Random session key (based on mouse movements and
keystrokes) is generated.
3.
Message encrypted with session key
4.
Session key is encrypted with receiver’s public key
5.
Encrypted message + encrypted session key sent via email
6.
Recipient uses their private key to decrypt the session key
7.
Session key is used to decrypt the message
8.
Message decompressed
54
Campbell R. Harvey 2018
http://www.pgpi.org/doc/pgpintro/
References
•
The Math Behind Bitcoin
[recommended]
•
Elliptic Curve Digital Signature Algorithm
(Bitcoin)
•
What does the curve used in Bitcoin, secp256k1, look like?
•
Elliptic Curve Digital Signature Algorithm
(Wikipedia)
•
Elliptic Curve Cryptography
(UCSB)
•
Elliptic Curve Cryptography and Digital Rights Managemen
t (Purdue)
•
Zero to ECC in 30 minutes
(Entrust)
•
The Elliptic Curve Cryptosystem
•
Goldwasser, Shaffi and Mihir Bellare, 2008,
Lecture Notes on Cryptography
•
Dan Boneh, Stanford University,
Introduction to Cryptography
•
Dan Boneh, Stanford University,
Cryptography II
•
https://arstechnica.com/security/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/
55
Campbell R. Harvey 2018
Cryptography, a vital part of digital communication, involves safeguarding messages from adversaries like eavesdroppers and impostors. Initially reliant on symmetric keys for encryption and decryption, the need to securely share keys posed a challenge. Technologies like DES and AES have advanced cryptographic methods, replacing older techniques like Enigma Machines. Enhancing data security is crucial to prevent unauthorized access and manipulation of sensitive information.
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
Innovation and Cryptoventures Digital Signatures Campbell R. Harvey Duke University and NBER January 19, 2018
Definition Cryptography is the science of communication in the presence of an adversary. Part of the field of cryptology. Campbell R. Harvey 2018 2
Goals of Adversary Alice sends message to Bob Eve is the adversary Campbell R. Harvey 2018 3
Goals of Adversary Eve s goals could be: 1. Eavesdrop 2. Steal secret key so that all future messages can be intercepted 3. Change Alice s message to Bob 4. Masquerade as Alice in communicating to Bob Campbell R. Harvey 2018 4
Symmetric Keys Early algorithms were based on symmetric keys. This meant a common key encrypted and decrypted the message You needed to share the common key and this proved difficult Campbell R. Harvey 2018 5
Symmetric Keys Early methods relied on a shared key or code A message would be encrypted and sent but the receiver needed to decode with a key or a special machine Example: The Lektor in James Bond, From Russia with Love. Campbell R. Harvey 2018 6
Symmetric Keys However, you needed to securely share the key or decoder. Campbell R. Harvey 2018 7
Symmetric Keys However, you needed to securely share the key or decoder. The adversary Campbell R. Harvey 2018 8
Symmetric Keys Nazi Enigma Machine is an earlier version of the Lektor https://www.youtube.com/watch?v=G2_Q9FoD-oQ https://www.youtube.com/watch?v=V4V2bpZlqx8 Recommended videos! Campbell R. Harvey 2018 9
Secret Keys Symmetric key DES (Data Encryption Standard) was a popular symmetric key method, initially used in SET (first on-line credit card protocol) DES has been replaced by AES (Advanced Encryption Standard) Campbell R. Harvey 2018 10
Diffee-Hellman Key Exchange Breakthrough in 1976 with Diffie-Hellman-Merkle key exchange There is public information that everyone can see. Each person, say Alice and Bob, have secret information. The public and secret information is combined in a way to reveal a single secret key that only they know https://www.youtube.com/watch?v=YEBfamv-_do Campbell R. Harvey 2018 11
Diffee-Hellman Key Exchange Will use prime numbers and modulo arithmetic We already encountered one example of modular arithmetic in the SHA-256 which uses mod=232 or 4,294,967,296 https://www.youtube.com/watch?v=YEBfamv-_do Campbell R. Harvey 2018 12
Key Exchange Numerical example 5 mod 2 = 1 Divide 5 by 2 the maximum number of times (2) 2 is the modulus The remainder is 1 Remainders never larger than (mod-1) so for mod 12 (clock) you would never see remainders greater than 11. EXCEL function = mod(number, divisor) e.g., mod(329, 17) = 6 mod Campbell R. Harvey 2018 13
Key Exchange Alice and Bob decide on two public pieces for information A modulus (say 17) A generator (or the base for an exponent) (say 3) Alice has a private key (15) Bob has a private key (13) Is it possible for them to share a common secret that is unlikely to be intercepted? Campbell R. Harvey 2018 14 https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/diffie-hellman-key-exchange-part-2
Key Exchange Alice: Calculates 315 mod 17 = 6 (i.e., =mod(3^(15), 17)) Alice send the message 6 to Bob Campbell R. Harvey 2018 15
Key Exchange Alice: Calculates 315 mod 17 = 6 (i.e., =mod(3^(15), 17)) Alice send the message 6 to Bob Eve intercepts the message! Campbell R. Harvey 2018 16
Key Exchange Bob: Calculates 313 mod 17 = 12 (i.e., =mod(3^(13), 17)) Bob send the message 12 to Alice Campbell R. Harvey 2018 17
Key Exchange Bob: Calculates 313 mod 17 = 12 (i.e., =mod(3^(13), 17)) Bob send the message 12 to Alice Eve intercepts the message! Now Eve has the 6 and the 12. Campbell R. Harvey 2018 18
Key Exchange Alice: Takes Bob s message of 12 and raises it to the power of her private key. Calculates 1215 mod 17 = 10 (i.e., =mod(12^(15), 17))* This is their common secret Campbell R. Harvey 2018 19 *EXCEL only does 15 digits so this will not work
Key Exchange Bob: Takes Alice s message of 6 and raises it to the power of his private key. Calculates 613 mod 17 = 10 (i.e., =mod(6^(13), 17)) This is their common secret Campbell R. Harvey 2018 20
Key Exchange Eve She has intercepted their message. However, without the common secret key, there is little chance she can recover the shared secret. Campbell R. Harvey 2018 21
Key Exchange Common secret Alice can now encrypt a message with the common secret and Bob can decrypt it with the common secret. Notice this is a common secret. Next we will talk private/public keys. That is, both and Alice have separate public keys and separate private keys. Campbell R. Harvey 2018 22
Key Exchange (Optional slide) Why does this work They are solving the same problem. Alice sent Bob 315 mod 17 = 6. Bob raises the to power of 13. This is the same as 613 mod 17 = [315]^(13) mod 17 =10 Alice s original calculation Campbell R. Harvey 2018 23
Key Exchange (Optional slide) Why does this work They are solving the same problem. Bob sent Alice 313 mod 17 = 12. Alice raises the to power of 15. This is the same as 1215 mod 17 = [313]^(15) mod 17 =10 Bob s original calculation Campbell R. Harvey 2018 24
Key Exchange (Optional slide) Why does this work They are solving the same problem. The modular arithmetic is crucial. See! [313]^(15) = [315]^(13) Campbell R. Harvey 2018 25
Key Exchange RSA and ECC Now we will introduce key pairs. The basic idea of modular arithmetic provides the foundation for RSA private/public key cryptography. The prime numbers that are used are huge. Private keys are mathematically linked to public keys. Campbell R. Harvey 2018 26
RSA: High Level Overview See my Cryptography 101 deck for much more detail. Two prime numbers are chosen and they are secret (say 7 and 13, called p, q). Multiply them together. The product (N=91) is public but people don t know the prime numbers used to get it. A public key is chosen (say 5). Given the two prime numbers, 7 and 13, and the public key, we can derive the private key, which is 29. Campbell R. Harvey 2018 27
RSA Issues with RSA RSA relies on factoring N is public (our example was 91) If you can guess the factors, p, q, then you can discover the private key Campbell R. Harvey 2018 28
RSA Issues with RSA Factoring algorithms have become very efficient To make things worse, the algorithms become more efficient as the size of the N increases Hence, larger and larger numbers are needed for N This creates issues for mobile and low power devices that lack the computational power Campbell R. Harvey 2018 29 http://www.slate.com/articles/health_and_science/science/2016/01/the_world_s_largest_prime_number_has_22_338_618_digits_here_s_why_you_should.html
Elliptic Curve Cryptography Mathematics of elliptic curves Does not rely on factoring Curve takes the form of y2 = x3 + ax + b Note that diagram is continuous but we will be using discrete versions of this arithmetic Note: 4a3 + 27b2 0 Bitcoin uses a=0 and b=7 Campbell R. Harvey 2018 30
Elliptic Curve Cryptography Properties Symmetric in x-axis Any non-vertical line intersects in three points Algebraic representation Campbell R. Harvey 2018 31
Elliptic Curve Cryptography Properties: Addition Define a system of addition . To add P and Q pass a line through and intersect at third point R . Drop a vertical line down to symmetric part. This defines P+Q (usually denoted ? ?) R P Q P+Q Denote Elliptic Curve as E Campbell R. Harvey 2018 32
Elliptic Curve Cryptography Properties: Doubling Define a system of addition . To add P and P use a tangent line and intersect at third point. Drop a vertical line down to symmetric part. This definite 2P (usually denoted ? ?) P Denote Elliptic Curve as E 2P Campbell R. Harvey 2018 33
Elliptic Curve Cryptography (Optional slide) Properties: Other (a) P + O = O + P = P for all P E. (existence of identity) (b) P + ( P) = O for all P E. (existence of inverse) (c) P + (Q + R) = (P + Q) + R for all P, Q, R E. (associative) (d) P + Q = Q + P for all P, Q E (communativity) Denote Elliptic Curve as E Campbell R. Harvey 2018 34
Elliptic Curve Cryptography (Optional slide) Why use in cryptography? Suggested by Koblitz and Miller in 1985 Implemented in 2005 Key insight: Adding and doubling on the elliptic curve is easy but undoing the adding is very difficult Campbell R. Harvey 2018 35
Elliptic Curve Cryptography (Optional slide) Modulo arithmetic on EC Example of modulo 67 (means only points are between 0 and 66 Notice the symmetry Campbell R. Harvey 2018 36 http://www.coindesk.com/math-behind-bitcoin/#
Elliptic Curve Cryptography (Optional slide) Modulo arithmetic on EC Notice the symmetry (reflection in the red line) Campbell R. Harvey 2018 37 http://www.coindesk.com/math-behind-bitcoin/#
Elliptic Curve Cryptography (Optional slide) Modulo arithmetic on EC Example of modulo 67 Addition of (2,22) and (6,25) Note (2,22) called the base point The dashed blue line wraps around and intersects at (47,39) and the reflection is (47,28) Campbell R. Harvey 2018 38 http://www.coindesk.com/math-behind-bitcoin/#
Elliptic Curve Cryptography (Optional slide) Modulo arithmetic on EC Example of modulo 67 Addition of (2,22) and (6,25) Note (2,22) called the base point The dashed blue line wraps around and intersects at (47,39) and the reflection is (47,28) Campbell R. Harvey 2018 39 http://www.coindesk.com/math-behind-bitcoin/#
Elliptic Curve Cryptography (Optional slide) Four choices: Form of elliptic curve Prime modulo Base point Order Campbell R. Harvey 2018 40 http://www.coindesk.com/math-behind-bitcoin/#
Elliptic Curve Cryptography (Optional slide) Four choices: Form of elliptic curve: y2= x3+ 7 Prime modulo: 2256 232 29 28 27 26 24- 1 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F Base point: 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8 Order: FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 Campbell R. Harvey 2018 41 http://www.coindesk.com/math-behind-bitcoin/#
Elliptic Curve Cryptography (Optional slide) How it works: Private key is a random number chosen between 1 and the order Public key = private key*base point Maximum number of private keys (and bitcoin addresses) is equal to the order. It is straightforward to go from private key to a public key but brutally difficult to go from public key to private key. Campbell R. Harvey 2018 42 http://www.coindesk.com/math-behind-bitcoin/#
Elliptic Curve Cryptography (Optional slide) How it works: 1. Choose private key and derive public key Let prime modulus = m Let base point (x,y) = G Let order = n Let private key = d (which is just a number) Public key Q(x,y) = d*G [operations on the elliptic curve with prime modulus m] Campbell R. Harvey 2018 43 http://www.coindesk.com/math-behind-bitcoin/#
Elliptic Curve Cryptography (Optional slide) How it works: 2. Sign Let data = z (which could be a SHA-256 of the data you are signing) Generate a random number k Calculate k*G which leads to particular coordinates (x,y)* Calculate r = x mod n [Note n=order] Calculate s = (z + r*d)/k mod n Private key Digital Signature (DS) = (r, s) is just a set of coordinates Campbell R. Harvey 2018 44 *I am not sure what modulus is used for this EC operation. http://www.coindesk.com/math-behind-bitcoin/#
Elliptic Curve Cryptography (Optional slide) How it works: 3. Verify Calculate w = s-1 mod n Calculate u = z*w mod n Calculate v = r*w mod n Calculate the point (x , y ) = uG + vQ Verify that r = x mod n If yes, verified. Base point Public key Remember DS = (r, s) Campbell R. Harvey 2018 45 http://www.coindesk.com/math-behind-bitcoin/#
Elliptic Curve Cryptography (Optional slide) How it works: 4. Intuition Anyone can encrypt something with a public key The digital signature algorithm uses the data, a random number, and both the private and public keys Verification shows that only the owner of both the private and public key could have signed. Verification is a yes or a no . Campbell R. Harvey 2018 46 http://www.coindesk.com/math-behind-bitcoin/#
ECDSA Private key is a number called signing key (SK). It is secret. Public key is the verification key and is mathematically linked to the private key VK EC SK Elliptic curve operations: Need base point, modulus, order Public key: coordinate (x, y) Private key: (number) Note: Easy to generate a public key with a private key. Not easy to go the other way. Campbell R. Harvey 2018 47
ECDSA Digital signature Nonce: (random number) Nonce EC DS Message SK Digital signature: coordinate (r, s) Elliptic curve operations: Need base point, modulus, order (n) Private key: (number) Campbell R. Harvey 2018 48
ECDSA Verification DS coordinates Yes r (verified) s EC (x , y ) r = x mod n ? Message No (rejected) VK Elliptic curve operations: Need base point, order (n) Derive new point on elliptic curve Check x coordinate of new point and DS Public key: (x, y) Campbell R. Harvey 2018 49
How DSAs Work Notice Proves that the person with the private key (that generated the public key) signed the message. Interestingly, digital signature is different from a usual signature in that it depends on the message, i.e., the signature is different for each different message. In practice, we do not sign the message, we sign a cryptographic hash of the message. This means that the size of the input is the same no matter how long the message is. Campbell R. Harvey 2018 50
