- Home
- INTERMEDIATE ALGEBRA
- Course Syllabus for Algebra I
- Mid-Plains Community College
- FRACTION OF A WHOLE NUMBER
- Systems of Linear Equations
- MATH FIELD DAY
- Course Outline for Finite Mathematics
- Calculus
- Algebra Final Examination
- Math 310 Exam #2
- Review of Trigonometric Functions
- Math 118 Practice test
- Precalculus Review
- Section 12
- Literal Equations
- Calculus Term Definitions
- Math 327A Exercise 2
- Public Key Algorithms II
- Maximizing Triangle Area
- Precalculus I Review for Midterm
- REVIEW OF A FIRST COURSE IN LINEAR ALGEBRA
- Math 6310 Homework 5
- Some Proofs of the Existence of Irrational Numbers
- ALGEBRAIC PROPERTIES OF MATRIX OPERATIONS
- Math 142 - Chapter 2 Lecture Notes
- Math 112 syllabus
- Math 371 Problem Set
- Complex Numbers,Complex Functions and Contour Integrals
- APPLICATIONS OF LINEAR EQUATIONS
- Week 4 Math
- Fractions
- Investigating Liner Equations Using Graphing Calculator
- MATH 23 FINAL EXAM REVIEW
- Algebra 1
- PYTHAGOREAN THEOREM AND DISTANCE FORMULA
- Georgia Performance Standards Framework for Mathematics - Grade 6
- Intermediate Algebra
- Introduction to Fractions
- FACTORINGS OF QUADRATIC FUNCTIONS
- Elementary Algebra Syllabus
- Description of Mathematics
- Integration Review Solutions
- College Algebra - Applications
- A Tip Sheet on GREATEST COMMON FACTOR
- Syllabus for Elementary Algebra
- College Algebra II and Analytic Geometry
- Functions
- BASIC MATHEMATICS
- Quadratic Equations
- Language Arts, Math, Science, Social Studies, Char
- Fractions and Decimals
- ON SOLUTIONS OF LINEAR EQUATIONS
- Math 35 Practice Final
- Solving Equations
- Introduction to Symbolic Computation
- Course Syllabus for Math 935
- Fractions
- Fabulous Fractions
- Archimedean Property and Distribution of Q in R
- Algebra for Calculus
- Math112 Practice Test #2
- College Algebra and Trigonometry
- ALGEBRA 1A TASKS
- Description of Mathematics
- Simplifying Expressions
- Imaginary and Complex Numbers
- Building and Teaching a Math Enhancement
- Math Problems
- Algebra of Matrices Systems of Linear Equations
- Survey of Algebra
- Approximation of irrational numbers
- More about Quadratic Functions
- Long Division
- Algebraic Properties of Matrix Operation
- MATH 101 Intermediate Algebra
- Rational Number Project
- Departmental Syllabus for Finite Mathematics
- WRITTEN HOMEWORK ASSIGNMENT
- Description of Mathematics
- Rationalize Denominators
- Math Proficiency Placement Exam
- linear Equations
- Description of Mathematics & Statistics
- Systems of Linear Equations
- Algebraic Thinking
- Study Sheets - Decimals
- An Overview of Babylonian Mathematics
- Mathematics 115 - College Algebra
- Complex Numbers,Complex Functions and Contour Integrals
- Growing Circles
- Algebra II Course Curriculum
- The Natural Logarithmic Function: Integration
- Rational Expressions
- QUANTITATIVE METHODS
- Basic Facts about Rational Funct
- Statistics
- MAT 1033 FINAL WORKSHOP REVIEW
- Measurements Significant figures
- Pre-Calculus 1
- Compositions and Inverses of Functions

# 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: g^{q} = 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 = g^{S} mod p for S < q

• Choose a per message public/private key pair

<T_{m}, S_{m}> with random S_{m} for message m

• T_{m} = (g^{Sm} mod p) mod q

• Calculate S_{m}^{-1 } mod q , so it won’t need to be done

in real time when signing a message

• Calculate a digest of the message d_{m} = SHS (m)

• SHS – a hashing function recommended by NIST for

use with DSS. SHS hashes to 160 bits

• Signature mod q

• Transmit m, T_{m}, X

• Public key information T, p, q, and g are known

beforehand

• Verify:

• Compute X^{-1} mod q

• Compute d_{m}

• x= d_{m} X^{-1} mod q

• y= T_{m} X^{-1} mod q

• z = (g^{x} T^{y} mod p) mod q

• if z = T_{m}, 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 (S_{m})!

• If S_{m} known, S can be computed

• Two messages sharing the same S_{m} can reveal

S_{m}, and thus S

## Per message Secret Number

• How is the private key exposed if the secret number

per message is known?

• If S_{m} is known, one can compute:

• (X_{m} S_{m} – d_{m}) T_{m}^{-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 S_{m}

• One can compute:

(X_{m} – X_{m}’ )^{-1} ( d_{m} - d_{m’} ) mod q = S_{m} 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

## 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 G_{i} and sends to Bob

• Bob → Alice: how did A or B → G_{i} ?

• Zero-knowledge: Bob knows nothing about the mapping

between A and B

• Fred can generate G_{i} 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 r_{1} …, r_{k}

• Alice sends r_{i}^2 mod n

• Bob chooses a random subset 1 of r_{i}^2, the rest is

subset 2

• For subset 1, Alice sends sr_{i} mod n, and Bob

verifies (sr_{i})^2 mod n = vr_{i}^2 mod n

• For subset 2, Alice simply sends r_{i} 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 (r_{i}^2, sr_{i})?

• If only (r_{i}^2, sr_{i}) was used

• If Fred has overheard Alice providing (r_{i}^2, sr_{i}), 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