Overview of Digital Signature, Cyber Security
Products & Solutions Demo
Dr Om Pal, Associate Professor
Dept of Computer Science,
University of Delhi
Hash Function
A cryptographic hash function h takes as input a message of
arbitrary length and produces as output a message digest of
fixed length.
…..0001111100011100000011111111001011100011...... Long message
Hash Function
1001010…..001101 Fixed length message digest
Let m is message and h(m) is message digest.
h is a one-way function.
Secure Hash Algorithm-1(SHA-1), SHA-256, Message Digest
(MD2,MD4,MD5 etc)
Hash Function
Pre-image resistant: h is a one-way or pre-image resistant hash
function if given a y, it is computationally infeasible to find an m
with h(m)=y.
Strongly collision-free: It is computationally infeasible to find
messages m1 and m2 with h(m1) = h(m2).
Birthday Attack: Let there are 23 people in a room. Now
probability of having unique birthday of each is
1.(1-1/365).(1-2/365).(1-3/365).....(1-22/365) = 0.493
So, probability of at least two have same birthday is 1-0.493
=0.507.
Therefore, select the suitable length of the hash for avoiding
collision.
Digital Signatures : Introduction
In the Middle Ages, a nobleman sealed a document with a wax
imprint of his insignia.
Why can’t we simply digitize our signature and append it to the
document? Can this signature be attached to another document?
Digital signatures can’t be separated from the message and
attached to another?
Digital signature is not only tied to the signer but also to the
message that is being signed.
Digital signatures are easily verified by the other parties.
Digital signature schemes consists two steps 1. Signing process
2. Verification Process
Digital Signatures : Introduction
The private-key signs (create) signatures, and the public-key
verifies signatures
Only the owner can create the digital signature, hence it can be
used to verify who created a message
Generally don't sign the whole message (doubling the size of
information exchanged), but just a digest or hash of the
message.
A signed message may be encrypted after it is signed. (if
confidentiality is required.
RSA Signature
Bob Has a document m that Alice agrees to sign. They do following-
Alice takes two large primes p, q and computes n=pq. She chooses eA
such that 1< eA <ø(n) with gcd( eA ,ø(n))=1 and calculate dA such that eA
dA ≡ 1 (mod ø(n)). Alice publishes (eA, n) and keep private dA , p, q.
Signing: Alice’s signature is
y ≡ mdA (mod n)
The pair (m, y) is then made public.
Verification: Bob verifies Alice’s signature as-
1. Download Alice’s (eA, n).
2. Calculate z ≡ yeA (mod n). If z=m, then Bob accepts the signature as valid;
otherwise signature is invalid.
RSA Blind Signature
Bob Has a document m. Alice signs the document without
knowing the content. They do following-
Alice takes two large primes p, q and computes n=pq. She
chooses eA such that 1< eA <ø(n) with gcd( eA ,ø(n))=1 and
calculate dA such that eA dA ≡ 1 (mod ø(n)). Alice publishes (eA,
n) and keep private dA , p, q.
Bob chooses a random integer k (mod n) with gcd(k,n)=1 and
compute t ≡ mkeA (mod n). He sends t to Alice.
Signing:
1. Alice’s signs t by computing: s ≡ tdA (mod n). She returns s to Bob.
2. Bob computes s/k(mod n). This is the signed message mdA .
Verification: Let show that s/k is the signed message
s/k ≡ tdA /k ≡ mdAkeAdA /k ≡ mdA (mod n) which is the signed message.
ElGamal Signature Scheme
RSA’s strength is the difficulty of factorization of product of large primes.
ElGamal Signature scheme is based on Discrete log problem (DLP).
Let Alice wants to sign a message. She chooses a large prime p and a primitive
root α.
Alice chooses a secret integer a such that 1<a<p-1 and calculate β≡αa (mod p) .
Values of p, α, β are made public. Alice keeps ‘a’ as secret. It is difficult to an
adversary to determine a from (p, α, β) since DLP is considered difficult.
Message Signing phase: Let Alice signs a message m. She does following-
1. Select a secret random k such that gcd(k, p-1)=1
2. Computes r≡αk (mod p)
3. Computes s≡k-1 (m-ar) (mod p-1)
Verification phase: Bob can verify the signature as follows-
1. Bob download Alice’s public key (p, α, β).
2. Compute v1≡ βr rs(mod p) and v2≡ αm (mod p).
3. Signature is valid iff v1≡ v2 (mod p).
Correctness: Since s≡k-1 (m-ar) (mod p-1) so, sk≡(m-ar) (mod p-1) or m≡(sk+ar)
(mod p-1).
Therefore, v2≡ αm ≡ αsk+ar ≡ αarαks ≡ βrrs ≡ v1 (mod p).
Public Key Infrastructure (PKI)
PKI is a framework consisting of policies defining the rules under which the
cryptographic systems operate and procedures for generating and publishing
keys and certificates.
A certificate is a quantity of information that has been signed by its publisher,
who is called as Certification Authority (CA).
The IT Act provides for the Controller of Certifying Authorities(CCA) to license
and regulate the working of Certifying Authorities. The Certifying Authorities
(CAs) issue digital signature certificates for electronic authentication of users.
Often for efficiency CA authorizes various registration authorities (RA) to sign
certificates.
Public Key Infrastructure (PKI)
Let CA publishes identity certificates for Alice and Bob.
If Alice knows CA’s public key, then she can take encrypted identity certificate
for Bob that has been published by CA.
X.509 Certificate: At the top is a certification authority (CA).
These are often commercial companies such as VeriSign, GTE, AT&T, and
others.
Certification Hierarchy:
CA
RA
Client Client Client Client Client
Public Key Infrastructure (PKI)
CA’s certificate details:
Public Key Infrastructure (PKI)
Client’s certificate details:
Demo: https://learn.pkiindia.in/
Thank You
[email protected]
