Try the Free Math Solver or Scroll down to Tutorials!












Please use this form if you would like
to have this math solver on your website,
free of charge.

Public Key Algorithms II


• Digital Signature Standard - DSS
• Zero-knowledge Proof Systems

Digital Signature Standard (DSS)

• By NIST, designed by NSA
  • Proposed in 1991, approved in 1994
  • DSA – algorithm
  • DSS – standard
• Related to El Gamal
• Speeded up for signer rather than verifier: smart cards
• Controversy RSA vs. DSS
  • When DSS was proposed a lot of investments were made in RSA
  • DSS a royalty free standard
  • DSS key size initially 512 later 1024
  • Designed by NSA

DSS Algorithm

• Generate public: p (512 bit prime) and q (160 bit
prime): p = k*q + 1
  • This is a very expensive operation, but not often
• Generate public g≠1: gq = 1 mod p
  • Take a random h>1 get g = h
  • If g = 1, chose another h(p-1)/q
• Choose long-term public/private key pair <T, S>,
with random S
  • T = gS mod p for S < q

• Choose a per message public/private key pair
<Tm, Sm> with random Sm for message m
  • Tm = (gSm mod p) mod q
  • Calculate Sm-1 mod q , so it won’t need to be done
in real time when signing a message
• Calculate a digest of the message dm = SHS (m)
• SHS – a hashing function recommended by NIST for
use with DSS. SHS hashes to 160 bits

• Signature mod q
• Transmit m, Tm, X
• Public key information T, p, q, and g are known
• Verify:
  • Compute X-1 mod q
  • Compute dm
  • x= dm X-1 mod q
  • y= Tm X-1 mod q
  • z = (gx Ty mod p) mod q
  • if z = Tm, the signature is verified

Why Is DSS Secure

• No revealing of private key S
• Can’t forge a signature without S
• No duplicate messages with matched signature
• Can’t be tempered
• Need a per-message secret number (Sm)!
  • If Sm known, S can be computed
  • Two messages sharing the same Sm can reveal
Sm, and thus S

Per message Secret Number

• How is the private key exposed if the secret number
per message is known?
• If Sm is known, one can compute:
  • (Xm Sm – dm) Tm-1) mod q = S mod q
• How is the private key exposed when two messages
share the same secret number?
  • If m and m’ are signed using the same Sm
  • One can compute:
(Xm – Xm’ )-1  ( dm - dm’ ) mod q = Sm mod q
• How to generate random numbers?

How Secure are RSA and
Diffie-Hellman ?

• The security of RSA is based on the difficulty of
• The security of Diffie-Hellman is based on the
difficulty of resolving discrete log problems
• It has been proved that they are equivalently difficult
• The best known algorithms to resolve them are
subexponencial but superpolynomial
• That’s why a larger key size is required (1024bits)
compared to secret key (80 bits)

Elliptic Curve Cryptography ECC

• No known subexponential algorithms to break ECC
• So it is secure with much smaller key – improve
• An elliptic curve is a set of points satisfying an
equation of the form:
y^2 + ax + by = x^3 + dx +e
• Mathematical operation on two points in the set will
always produce a point in the set

Zero-Knowledge Proofs

• Alice: “I know the ingredients in McDonald’s secret
• Bob: “No, you don’t”
• Alice: “Yes, I do”
• Bob: “Prove it”
• Alice: “All right. I’ll tell you.” She whispers in Bob’s
• Bob: “Now I know it too. I will post in my web page”
• Alice: “Oops”

The Zero-knowledge Cave

The Zero-knowledge Cave

• 1. Bob stands at point A
• 2. Alice walks all the way into the cave, either to point
C or D
• 3. Bob walks to point B
• 4. Bob asks Alice to
  • Come out of the left passage
  • Come out of the right passage
• 5. Alice complies by using the magic word to open the
door C or D
• 6. Bob and Alice repeat steps 1-5 n times.

Zero-knowledge Proof Systems

• Prove knowledge without revealing it
• RSA signatures
• Graph isomorphism: rename vertices
  • Alice: graph A and B ~ A
  • Public key: graphs A, B
  • Private key: mapping between vertices
  • Alice: create Gi and sends to Bob
  • Bob → Alice: how did A or B → Gi ?
  • Zero-knowledge: Bob knows nothing about the mapping
between A and B
  • Fred can generate Gi from either A or B, but not both

Zero-knowledge Proofs:

• Alice: public key <n, v>, n=pq, private key s
  • Alice selects random number s, and computes v=s^2
mod n
• Alice chooses k random numbers r1 …, rk
• Alice sends ri^2 mod n
• Bob chooses a random subset 1 of ri^2, the rest is
subset 2
  • For subset 1, Alice sends sri mod n, and Bob
verifies (sri)^2 mod n = vri^2 mod n
  • For subset 2, Alice simply sends ri mod n
• Finding square root mod n is hard

• Suppose Fred wants to impersonate Alice
• Fred can compute squares mod n but cannot take
square roots mod n
• Fred can send random r and compute r^2, so he can give
correct answers for subset 2, but not for subset 1
• So what the purpose of subset 2? Why isn’t the
protocol simply that Alice sends pairs (ri^2, sri)?

• If only (ri^2, sri) was used
  • If Fred has overheard Alice providing (ri^2, sri), he
can impersonate Alice.
• But because both subsets are needed
  • Even if he knows subset 1 + answer and subset 2 +
answer, the probability of having the new subset 1’
equal to subset 1 is very small
  • For each I the probability is 50%, for the whole
subset (30) no chance to impersonate, on in ten


• Digital Signature Standard - DSS
• Zero-knowledge Proof Systems