Try the Free Math Solver or Scroll down to Tutorials!

 Depdendent Variable

 Number of equations to solve: 23456789
 Equ. #1:
 Equ. #2:

 Equ. #3:

 Equ. #4:

 Equ. #5:

 Equ. #6:

 Equ. #7:

 Equ. #8:

 Equ. #9:

 Solve for:

 Dependent Variable

 Number of inequalities to solve: 23456789
 Ineq. #1:
 Ineq. #2:

 Ineq. #3:

 Ineq. #4:

 Ineq. #5:

 Ineq. #6:

 Ineq. #7:

 Ineq. #8:

 Ineq. #9:

 Solve for:

 Please use this form if you would like to have this math solver on your website, free of charge. Name: Email: Your Website: Msg:

# Public Key Algorithms II

## Overview

• 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
beforehand
• 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
factoring
• 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
performance
• 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
sauce”
• Bob: “No, you don’t”
• Alice: “Yes, I do”
• Bob: “Prove it”
• Alice: “All right. I’ll tell you.” She whispers in Bob’s
ear”
• Bob: “Now I know it too. I will post in my web page”
• Alice: “Oops”

## 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: Fiat-Shamir

• 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
billion

## Summary

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