Digital Signatures

Yosua Alvin, M.Eng.

Electrical Engineering Department
Diponegoro University
 2

Why public key cryptography?

With secret key algorithms

Number of key pairs to be generated is extremely large
If there is a conflict between Alice and Bob, it is hard to
resolve it
Non-repudiation
Why not public key algorithms?
Slow, computationally intensive
 Public key encryption revisited

Alice Insecure channel Bob

x y x

kubob krbob

What security services does it provide?

Confidentiality/Privacy
Authentication
Integrity
Non-repudiation
3
 4

What happens if we use the keys of both

sender and receiver
Alice Bob

x u y y u x

KRA KUB KRB KUA

What security services does this provide?

Can Oscar generate u?
Can Bob generate u?
 5

Digital Signatures

Recap
Message authentication provides security services of
authentication and integrity
It does not provide non-repudiation
Digital signatures
Should provide us the same functionality as regular
signatures
Must depend on the message
Binding the signature to the message
Must be information unique to the signer that cannot be
forged
 6

Digital Signature
Anyone can verify the signature with the public key
No one else can generate a signature since the private
key is know only to the owner

Alice Bob

Sig(x)
x

x
KUA

KRA
Compare
 7

How does a signature differ from a MAC or

simple encryption?
A MAC is used to ensure message authentication
The attack is to successfully change the message or create a
false message without detection
A signature is used to sign a digital document
Goals of a successful attack
Total Break
Oscar can determine Alices private key
Selective Forgery
With some probability, create a forged signature for a
message that Alice has not previously signed
Existential Forgery
Change the document but enable the signature to be
verified
Create a false document and signature pair such that the
signature is verified
 8

Attacks against Digital Signatures

Key only attack

Similar to ciphertext-only attack, but Oscar knows the
public key
Known message attack
Similar to known plaintext attack
Oscar has pairs of messages and signatures
Chosen message attack
Oscar can choose the messages that Alice will sign
 RSA Digital Signature
Alice Sig(x) Bob
x

x
KUA
Sig(x)
KRA
Compare
Setup:
Public key: KU ={n, b}
Private key: KR = {p, q, a}
Here a b = 1 mod (n)
(n) = (p 1)(q 1)

9
 10

RSA Signature Protocol

Alice computes sigKRA(x) = xa mod n = u
Alice sends Bob x || u
Bob verifies the signature as follows:
He decrypts the signature first
Compute verKUA(u) = ub mod n = x*
Compare x and x*
Remarks:
Only Alice can sign her documents
Anyone can verify it
Bob is assured the message is from Alice
If the message is altered, the signature will reveal
this
Signature provides authentication, integrity, and non-
repudiation
 11

Drawbacks

Long message => long signature

Solution: Hash the message before signing it
Oscar can choose a signature and compute a
plaintext from it
Choose signature u
Compute plaintext x = eKUA(u) = ub mod n
Send x||u to Bob
The message may be meaningless, but it will appear to
have come from Alice
RSA signature is used in the ISO/IEC 9796 standard
 12

How Digital Signatures are generated

using Hash functions

Alice y
x
d
x x
kAB kAB
eKR[ h(x) ]

kuA
Hash Bob
Or MAC
krA Verify
x || e KR[ h(x) ]
Skema pada Digital Signature
Bila Pengirim sebagai inisiator dibantu
menggunakan random session key
Pada skema lain bisa juga messagenya tidak
dienkripsi namun untuk memastikan keabsahan
cukup mengenkripsi hashnya menggunakan private
key dari pengirim
Hybrid Digital Signature using AES
Contoh Pemakaian RSA
Cari kode ciphertext dari proses enkripsi dan plain text dari proses
dekripsi, dengan menggunakan algoritma teknik enkripsi RSA (Rivest,
Shamir, Adelman). Plain text yang dijadikan input adalah nama anda
dan untuk nilai N, Ks dan Kp harus ditentukan sebelumnya.

1. Menentukan nilai p dan q secara acak dimana untuk syarat

penentuan nilai p danq merupakan bebas yang termasuk bilangan
prima.
- p bernilai 13
- q bernilai 31

2. Hitung modulus n (public key) dan fungsi Eulers Totient (n)

dengan rumus
-n=pxq
= 13 x 31
= 403

- (n) = (p 1) (q 1)
= (13 1) (31 1)
= 12 x 30
= 360
3. Menentukan nilai Kp. Karena nilai Kp tidak boleh merupakan nilai factorial dari
(n) yang bersifat bilangan prima, maka sebelumnya dicari nilai factorial dari
(n), yaitu :
- (n) = 360
= 2^3 x 3^2 x 5

Jadi untuk nilai Kp tidak boleh bernilai 2, 3 atau 5. Dan disini ditentukan Kp = 7

4. Menentukan nilai Ks, Nilai Ks dapat ditentukan dengan rumus sebagai berikut :
(Kp x Ks) mod (n) = 1
(7 x Ks) mod 360 = 1
Sehingga untuk menentukan nilai Ks dengan cara termudah adalah
Ks = "(m x 360 + 1)" /1 = 1

Hasil dari Ks adalah bilangan bulat dengan mencoba nilai-nilai m (bilangan

integer) = 1, 2, 3, , sehingga diperoleh Ks adalah 103 dengan m = 2
5. Cek nilai Ks
(7 x Ks) mod 360 = 1
(7 x 103) mod 360 = 1
721 mod 360 = 1

kemudian
(721 -1) / 360 = modulo 0
720 / 360 = 2 modulo 0
Jadi dapat ditentukan bahwa nilai Ks adalah 103.

6. Setelah didapat semua parameter yang akan digunakan dalam proses

enkripsi dan dekripsi, yaitu :
n = 403 ;
Kp = 7 ;
Ks = 103 ;
ENKRIPSI

Enkripsi (chipper code) = (Character)Kp mod n

M = 777 mod 403 = 116

A = 657 mod 403 = 234
R = 827 mod 403 = 173
I = 737 mod 403 = 44
B = 667 mod 403 = 326
E = 697 mod 403 = 121
L = 767 mod 403 = 236
A = 657 mod 403 = 234
J = 747 mod 403 = 334
A = 657 mod 403 = 234
R = 827 mod 403 = 173
DEKRIPSI
Dekripisi (Plain text) = (Chipper code)Ks mod n

M = 116103 mod 403 = 77

A = 234103 mod 403 = 65
R = 173103 mod 403 = 82
I = 44103 mod 403 = 73
B = 326103 mod 403 = 66
E = 121103 mod 403 = 69
L = 236103 mod 403 = 76
A = 234103 mod 403 = 65
J = 334103 mod 403 = 74
A = 234103 mod 403 = 65
R = 173103 mod 403 = 82
 13

ElGamal Signature Scheme

Different from ElGamal Encryption Scheme

Published in 1985
A variation of this forms the Digital Signature Standard
(DSS)
Not useful for encryption, but only for signatures
 14

Setup

Choose a large prime number p

Choose a generator Zp*
Choose a private key KR = a {2,3,4,,p 2}
Compute the public key KU = b = a mod p
Keys:
Public: KU ={p, , b}
Private: KR = {a}
 15

Signing with private key

Choose a random number k Zp-1*

This means
k < p-1
GCD(k, p-1) = 1

Compute the signature of the message x as

sigKR(x) = (,) where
= k mod p
= (x - a )k-1 mod (p-1)
 16

Public Verification

The verification function is:

VerKU(x, (,) )
Check if b = x mod p
If true, the signature is valid
If false, the signature is invalid
 17

Why does it work?

What is b ?
What is b?
b = a
b = a
What is ?

Verification gives
a x - a = x
 19

Security of ElGamal Signature Scheme

What is an attack on signatures?
Oscar can generate a fake signature
Oscar can break the signing scheme to get a
knowledge of the private key
Oscar can choose and then try to find
DL Problem
Oscar can choose and try to find
Generally considered infeasible
Oscar can choose and and try to come up with
a random plaintext x as with the RSA signature
scheme
DL Problem
 20

Drawbacks

Long message => long signature

If the value of k is used repeatedly, the signature scheme
becomes insecure
 21

The Digital Signature Standard

Based on the Digital Signature Algorithm (DSA)

A variation of the ElGamal signature scheme
See Textbook, page 294-297
Sign the hash value of a signature to keep it small
The 160 bit SHA based hash value is signed with a
320 bit signature
The value of p is around 2512 to 21024
Published in 1993 as a NIST FIPS PUBS 186 standard
 22

Modular Roots
Definition
Let m,n be natural numbers, c be an integer and gcd(c,n)
=1
Let xm = c mod n for some integer x
Then x is called the m-th root of c modulo n
And c is called an m-th power residue modulo n
Example: x2 = c mod n
x is called a square root mod n
c is called a quadratic residue mod n
If the prime factors of n are known, then
We can use CRT to find the m-th roots modulo n
Otherwise, it is considered to be a hard problem, as hard
as integer factorization for large n
You can also have the m-th root modulo a prime number
 23

Schnorr Signature Scheme

Setup
Choose a large prime number p
Choose a prime number q that divides p -1
Choose a number Zp* that is the q-th root of 1 mod p
What is the order of ?
Choose a private key KR = a {2,3,4,,q 1}
Compute the public key KU = b = a mod p
Keys:
Public: KU ={p, q, , b}
Private: KR = {a}
Let h(.) be a secure hash function (e.g., SHA-1 or RIPE-MD)
 24

Signing with private key

Choose a random number k Zq*

This means
0<k<q
Compute the signature of the message x as
sigKR(x, k) = (,) where
= h (x || k )
= k + a mod q
 25

Public Verification

The verification function is:

VerKU(x, (,) )
Check if
h(x || b- ) =
If true, the signature is valid
If false, the signature is invalid
Why does this work?
What is b- mod p ?
 26

Digital Signature Algorithm

Setup
Choose a prime number p that is L bits long where L is a
multiple of 64 bits, larger than 512 bits and smaller than
1024 bits

Choose a prime number q that divides p -1 and is 160 bits
long
Choose a number Zp* that is the q-th root of 1 mod p
What is the order of ?
Choose
Compute a the
private keykey
public KR KU
= a=b{2,3,4,,q
= a mod p1}
Keys:
Public: KU ={p, q, , b}
Private: KR = {a}
Let h(.) be the secure hash algorithm (SHA-1)
 27

Signing with private key

Choose a random number k Zq* is 160 bits

This means is log2 q bits
0<k<q They CANNOT
be zero
Compute the signature of the message x as
sigKR(x, k) = (,) where
= (k mod p) mod q
= (SHA-1(x) + a)k-1 mod q
 28

Public Verification

The verification function is: VerKU(x, (,) )

Compute
e1 = SHA-1(x) -1 mod q
e2 = -1 mod q
Check if: (e1 be2 mod p) mod q =
If true, the signature is valid
If false, the signature is invalid
Why does this work?
 29

ECDSA

ECDSA = Elliptic Curve Digital Signature Algorithm

It is identical to DSA, but uses Elliptic Curves instead
The notation is a little bit different, but the procedure is
identical
 30

Blind Signatures

Two party protocol between Alice and Bob

Alice sends Bob a piece of information
Bob signs the information and sends it back
to Alice
Alice can now compute Bobs signature
over another message m of her choice
After this is done, Bob does not know either
the message m or the signature associated
with it
 31

Other signature schemes

Undeniable signatures
Requires the cooperation of the signer to verify the
signature
One-time signature
A new public key is required for verification for each
signature
 32

Other References

http://www.epic.org/crypto/dss/
http://www.itl.nist.gov/fipspubs/fip186.htm