MATH 470 Lecture 19

« previous | Thursday, March 28, 2013 | next »

Tests will be graded by tomorrow, and are viewable during office hours on Monday 11:00 – 12:30

From Yesterday

The secret was 23:

Three pairs for group were:

• (12,96)
• (38,25)
• (2,17)

Randomness and Collisions: The Birthday Paradox

What are the chances that among 25 people, there exist at least 2 people with the same birthday?

Very likely: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 - Pr[\text{no common birthdays}]} , and the probability that there are no common birthdays is

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 \cdot \frac{364}{365} \cdot \frac{363}{365} \dots = \prod_{j=1}^{24} \left( 1 - \frac{j}{365} \right)}

With a little work, we can get an estimate:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \prod_{j=1}^{24} \left( 1 - \frac{j}{365} \right) \ge 1 - \mathrm{e}^{-\frac{25(25-1)}{2(365)}}}

Similarly, when picking Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} numbered balls (with replacement) out of an urn with $n$, the probability of getting a collision is at least

$1-\mathrm {e} ^{-{\frac {r(r-1)}{2n}}}$

Back to Signatures: Priority

This is an example of "Blind" Signatures

Suppose Pfizer and Roche are developing a cure for cancer. They are entering trials with patients, but want to later claim priority.

They want to prevent espionage by the other company.

If they want the CDC to believe their claim of priority, all parties can do the following:

Reveal that you know something without telling anyone what it is.

• CDC generates 2 RSA instances: $(p_{1},q_{1},n_{1},e_{1},d_{1})$ and $(p_{1},q_{1},n_{1},e_{1},d_{1})$.
• CDC sends set 1 $(n_{1},e_{1})$ to Pfizer and set 2 $(n_{2},e_{2})$ to Roche
• Pfizer picks a random $k_{1}\in \left(\mathbb {Z} /n_{1}\mathbb {Z} \right)^{*}$ and sends $t_{1}=k_{1}^{e_{1}}\,m_{1}{\pmod {n_{1}}}$ to the CDC.
• The CDC signs $t_{1}$ by computing $s_{1}=t_{1}^{d_{1}}{\pmod {n_{1}}}$ and sends it back to Pfizer
• Pfizer keeps $s_{1}/k_{1}$
• Roche does the same with subscript 2

Each message $m_{i}$ is the formula for the cancer drugs.

Assuming these dialogues happened today (28 Mar. 2013), when trials are done, Pfizer (or Roche) can say: "I was first!" and prove it:

Proof. Pfizer observes

${\frac {s_{1}}{k_{1}}}={\frac {t_{1}^{d_{1}}}{k_{1}}}={\frac {\left(k_{1}^{e_{1}}\,m_{1}\right)^{d_{1}}}{k_{1}}}=m_{1}^{d_{1}}$

CRC evaluates $\left(m_{1}\,d_{1}\right)^{e_{1}}=m_{1}$

Now in order for this to work, the CDC must be honest

Hash Functions

For digital signatures to be practical, we need to sign digests of messages instead of messages because RSA and El Gamal run in cubic time, not linear time (i.e. slow).

How do we get a digest?

Simple idea: use first few hundred bits

However, this can lead to collisions if two messages start with the same thing.

Mathematically, we want a function

$H:\left\{0,1\right\}^{N}\to \left\{0,1\right\}^{n}$

(maps bit strings of length $N$ to bit strings of length $n$)

such that

1. $H$ can be computed relatively quickly ($On)$)
2. $H$ is pre-image resistant, i.e. given $y$, finding $m'$ with $H(m')=y$ is very hard.
3. $H$ is strongly collision-free: it is very hard to find $m_{1}$ and $m_{2}$ with $H(m_{1})=H(m_{2})$

Note: For $N>n$ with $H$ having no collisions, this is impossible!

Note: requirements 2 and 3 are for cryptographic hash functions. For computing programming hashes for use in hash tables, requirements 2 and 3 may be discarded

Example Hash Functions

1. $H(m)=m{\pmod {n}}$
   • (1 passes) easy to compute
   • (2 fails) given Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} , it's easy to find Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m'} with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(m') = y} , namely Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m' = y} .
   • (3 fails) take Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(m_1) = H(m_1 + n)}
2. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(x) = \alpha^x \pmod{p}}
   • (1 passes) easy
   • (2 passes) discrete log is hard
   • (3 passes) only if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} is a generator for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p}
   • BUT range is still considerably big: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H(13081) \equiv 5^{13081} \equiv 103103 \pmod{104729}}

Digression: Transmitting Keys via RSA

Suppose you want to transmit a 56-bit (< 10¹⁷) DES key using RSA with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} having 200 bits (> 10⁶⁰).

You would like your adversary to be forced to search through all possibilities if she tries to read your message.

However, using RSA naïvely enables Eve to find the 56-bit key after searching just 2E9 possibilities!

1. Compute Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^{-e} \pmod{n}} for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y \in \{ 1, \ldots, 10^9 \}}
2. Upon seeing your message Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c = m^e} , she computes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c \, x^e} for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in \{ 1, \ldots, 10^9 \}}
3. Now Eve looks for collisions Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^{-e} = c\,x} by checking Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \binom{10^9}{2} \le 10^{18}} possibilities in total, BUT
4. Thanks to the birthday paradox, Eve will find a collision with probability 2E9 checks!

The collisions work because Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^{-e} = c \, x^e \iff c = (x\,y)^{-e} = ((x\,y)^{-1})^e} , and so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m = (x\,y)^{-1}}

Eve just found an encrypted key with relatively little work

What to do!?

Padding

Concatenate 72 random bits to the front and back of the key.

This still is not quite secure: Eve could figure out how the padding scheme works

OAEP-Padding Scheme

1994: Bellaire and Rogaway

Based on hash functions, but performs the inverse Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{ 0,1 \}^n \to \{0,1\}^N} mapping.