Part VI
Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash
functions
CHAPTER 6: Other cryptosystems , pseudo-random numbers generators
and hash functions
A large number of interesting and important cryptosystems have already been designed.
In this chapter we present some of them in order to illustrate principles and techniques
that can be used to design cryptosystems.
At first, we present several cryptosystems security of which is based on the fact that
computation of discrete logarithms is infeasible in some groups.
Secondly, we discuss pseudo-random number generators and hash functions
– other very important concepts of modern cryptography
Finally, we discuss one of the fundamental questions of modern cryptography:
when can a cryptosystem be considered as (computationally) perfectly secure?
In order to do that we will:
discuss the role randomness play in the cryptography;
introduce the very fundamental definitions of perfect security of cryptosystem
present some examples of perfectly secure cryptosystems.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 2/37
Rabin cryptosystem
Primes p, q of the form 4k + 3 are kept secret, n = pq is the public key.
Encryption: of a plaintext w < n
c = w2
mod n
Decryption: Using a method to compute w given c with Chinese remainder theorem one
can get that w equals to one of the numbers:
w1 = c(p+1)/4
mod n w2 = p − c(p+1)/4
mod n
w3 = c(q+1)/4
mod n w4 = q − c(q+1)/4
mod n
Indeed, it is easy to verify, using Euler’s criterion which says that if c is a quadratic
residue modulo p, then c(p−1)/2
≡ 1 (mod p), that
±c(p+1)/4
mod p and ±c(q+1)/4
mod q
are two square roots of c modulo p and q. One can now obtain four square roots of c
modulo n using the method shown in Appendix.
In case the plaintext w is a meaningful English text, it should be easy to determine w
from w1, w2, w3, w4.
However, if w is a random string (say, for a key exchange) it is impossible to determine
w from w1, w2, w3, w4.
Rabin did not propose this system as a practical cryptosystem.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 3/37
Generalized Rabin cryptosystem
Public key: n, B (0 ≤ B ≤ n − 1)
Trapdoor: primes p, q (n = pq) of the form 4k + 3
Encryption: e(x) = x(x + B) mod n
Decryption: d(y) =
„q
B2
4
+ y − B
2
«
mod n
It is easy to verify that if ω is a nontrivial square root of 1 modulo n, then there are four
decryptions of e(x):
x, −x, ω
`
x + B
2
´
− B
2
, −ω
`
x + B
2
´
− B
2
Example
e
`
ω
`
x + B
2
´
− B
2
´
=
`
ω
`
x + B
2
´
− B
2
´ `
ω
`
x + B
2
´
+ B
2
´
= ω2
`
x + B
2
´2
−
`B
2
´2
=
x2
+ Bx = e(x)
Decryption of the generalized Rabin cryptosystem can be reduced to the decryption of
the original Rabin cryptosystem.
Indeed, the equation => x2
+ Bx ≡ y (mod n)
can be transformed by the substitution x = x1 − B/2 => into
x1
2
≡ B2
/4 + y (mod n) and, by defining c = B2
/4 + y, => into x1
2
≡ c (mod n)
Decryption can be done by factoring n and solving congruences
x1
2
≡ c (mod p) x1
2
≡ c (mod q)
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 4/37
Security of Rabin cryptosystem
We show that any hypothetical decryption algorithm A for Rabin cryptosystem, can be
used, as an oracle, in the following Las Vegas algorithm, to factor an integer n.
Algorithm:
1 Choose a random r, 1 ≤ r ≤ n − 1;
2 Compute y = (r2
− B2
/4) mod n; {y = ek (r − B/2)}.
3 Call A(y), to obtain a decryption x =
„q
B2
4
+ y − B
2
«
mod n;
4 Compute x1 = x + B/2; {x1
2
≡ r2
mod n}
5 if x1 = ±r then quit (failure)
else gcd(x1 + r, n) = p or q
Indeed, after Step 4, either x1 = ±r mod n or x1 = ±ωr mod n.
In the second case we have
n | (x1 − r)(x1 + r),
but n does not divide either factor x1 − r or x1 + r.
Therefore computation of gcd(x1 + r, n) or gcd(x1 − r, n) must yield factors of n.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 5/37
ElGamal cryptosystem
Design: choose a large prime p – (with at least 150 digits).
choose two random integers 1 ≤ q, x < p – where q is a primitive element of Z∗
p
calculate y = qx
mod p.
Public key: p, q, y; trapdoor: x
Encryption of a plaintext w: choose a random r and compute
a = qr
mod p, b = yr
w mod p
Cryptotext: c = (a, b)
(Cryptotext contains indirectly r and the plaintext is masked by multiplying with yr
(and
taking modulo p))
Decryption: w = b
ax mod p = ba−x
mod p.
Proof of correctness: ax
≡ qrx
mod p
b
ax
≡
yr
w
ax
≡
qrx
w
qrx
≡ w(mod p)
Note: Security of the ElGamal cryptosystem is based on infeasibility of the discrete
logarithm computation.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 6/37
Shanks’ algorithm for discrete logarithm
Let m = sqrt(p − 1) . The following algorithm computes lgqy in Z∗
p.
Compute qmj
mod p, 0 ≤ j ≤ m − 1.
Create list L1 of m pairs (j, qmj
mod p), sorted by the second item.
Compute yq−i
mod p, 0 ≤ i ≤ m − 1.
Create list L2 of pairs (i, yq−i
mod p) sorted by the second item.
Find two pairs, one (j, z) ∈ L1 and second (i, z) ∈ L2
If such a search is successful, then
qmj
mod p = z = yq−i
mod p
and as the result
lgqy ≡ (mj + i) mod (p − 1).
Therefore
qmj+i
≡ y (mod p)
On the other hand, for any y we can write
lgqy = mj + i,
For some 0 ≤ i, j ≤ m − 1. Hence the search in the Step 5 of the algorithm has to be
successful.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 7/37
Bit security of discrete logarithm
Let us consider problem to compute Li (y) = i-th least significant bit of lgqy in Z∗
p.
Result 1 L1(y) can be computed efficiently.
To show that we use the fact that the set QR(p) has (p − 1)/2 elements.
Let q be a primitive element of Z∗
p. Clearly, qa
∈ QR(p) if a is even. Since the elements
q0
mod p, q2
mod p, . . . , qp−3
mod p
are all distinct, we have that
QR(p) = {q2i
mod p | 0 ≤ i ≤ (p − 3)/2}
Consequence: y is a quadratic residue iff lgqy is even, that is iff L1(y) = 0.
By Euler’s criterion y is a quadratic residue if y(p−1)/2
≡ 1 mod p
L1(y) can therefore be computed as follows:
L1(y) = 0 if y(p−1)/2
≡ 1 mod p;
L1(y) = 1 otherwise
Result 2 Efficient computability of Li (y), i > 1 in Z∗
p would imply efficient computability
of the discrete logarithm in Z∗
p.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 8/37
Williams cryptosystem – basics
Similar to RSA, but number operations are performed in a quadratic field. Cryptoanalysis
of Williams cryptosystem is equivalent to factoring.
Consider numbers of the form
α = a + b
√
c
where a, b, c are integers.
If c remains fixed, α can be viewed as a pair (a, b).
α1 + α2 = (a1, b1) + (a2, b2) = (a1 + a2, b1 + b2)
α1α2 = (a1, b1) · (a2, b2) = (a1a2+c b1b2, a1b2 + b1a2)
The conjugate α of α of a is defined by
α = a − b
√
c
Auxiliary functions: Xi (α) =
αi
+ α−i
2
Yi (α) =
b(αi
− α−i
)
(α − α)
„
=
α − αi
2
√
c
«
Hence
αi
= Xi (α) + Yi (α)
√
c
αi
= Xi (α) − Yi (α)
√
c
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 9/37
Williams cryptosystem – efficient exponentiation
Assume now
a2
− cb2
= 1
Then αα = 1 and consequently
XI
2
− cYI
2
= 1
Moreover, for j ≥ i
XI+J = 2XI XJ + XJ−1
YI+J = 2YI XJ + YJ−1
From these and following equations:
XI+J = 2XI XJ +cYI YJ
YI+J = 2YI XJ + XI YJ
we get the recursive formulas:
X2i = Xi
2
+ cYi
2
= 2Xi
2
− 1
Y2i = 2Xi Yi
X2i+1 = 2Xi Yi+1 − X1
Y2i+1 = 2Xi Yi+1 − Y1
Consequences: 1. Xi and Yi can be, given i, computed fast.
Remark Since X0 = 1, X1 = a, Xi does not depend on b.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 10/37
WHEN is a CRYPTOSYSTEM (perfectly) SECURE?
First question: Is it enough for perfect security of a cryptosystem that one cannot get a
plaintext from a cryptotext?
NO, NO, NO
WHY
For many applications it is crucial that no information about the plaintext could be
obtained.
Intuitively, a cryptosystem is (perfectly) secure if one cannot get any (new)
information about the corresponding plaintext from any cryptotext.
It is very nontrivial to define correctly when a cryptosystem is (computationally)
perfectly secure.
It has been shown that perfectly secure cryptosystems have to use randomized
encryptions.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 11/37
Cryptography and Randomness
Randomness and cryptography are deeply related.
1 Prime goal of any good encryption method is to transform even a highly nonrandom
plaintext into a highly random cryptotext. (Avalanche effect.)
Example Let ek be an encryption algorithm, x0 be a plaintext. And
xi = ek (xi−1), i ≥ 1.
It is intuitively clear that if encryption ek is “cryptographically secure”, then it is
very, very likely that the sequence x0 x1 x2 x3 is (quite) random.
Perfect encryption should therefore produce (quite) perfect (pseudo)randomness.
2 The other side of the relation is more complex. It is clear that perfect randomness
together with ONE-TIME PAD cryptosystem produces perfect secrecy. The price to
pay: a key as long as plaintext is needed.
The way out seems to be to use an encryption algorithm with a pseudo-random
generator to generate a long pseudo-random sequence from a short seed and to use
the resulting sequence with ONE-TIME PAD.
Basic question: When is a pseudo-random generator good enough for
cryptographical purposes?
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 12/37
Secure encryptions – basic concepts I
We now start to discuss a very nontrivial question: when is an encryption scheme
computationally perfectly SECURE?
First, some very basic technical concepts:
Definition A function f:N → R is a negligible function if for any polynomial p(n) it holds,
for almost all n:
f (n) ≤ 1
p(n)
Definition – computational distinguishibility Let X = {Xn}n∈N and Y = {Yn}n∈N be
probability ensembles such that each Xn and Yn ranges over strings of length n. We say
that X and Y are computationally indistinguishable if for every feasible algorithm A the
difference
dA(n) =| Pr[A(Xn) = 1] − Pr[A(Yn) = 1] |
is a negligible function in n.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 13/37
Secure encryptions – pseudorandom generators
In cryptography random sequences can be usually fully replaced by pseudorandom
sequences generated by (cryptographically perfect) pseudorandom generators.
Definition - pseudorandom generator. Let l(n) : N → N be such that l(n) > n for all n. A
(computationally indistinguishable) pseudorandom generator with stretch function l, is an
efficient deterministic algorithm which on input of a random n-bit seed outputs a l(n)-bit
sequence which is computationally indistinguishable from a random l(n)-bit sequence.
Theorem Let f be a one-way function which is length preserving and efficiently
computable, and b be a hard core predicate of f, then
G(s) = b(s) · b(f (s)) · · · b
“
f l(|s|)−1
(s)
”
is a (computationally indistinguishable) pseudorandom generator with stretch function
l(n).
Definition A predicate b is a hard core predicate of the function f if b is easy to evaluate,
but b(x) is hard to predict from f(x). (That is, it is unfeasible, given f(x) where x is
uniformly chosen, to predict b(x) substantially better than with the probability 1/2.)
It is conjectured that the least significant bit of the modular squaring function x2
mod n
is a hard-core predicate.
Theorem A (good) pseudorandom generator exists if a one-way function exists.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 14/37
Cryptographically strong pseudo-random generators
Fundamental question: when is a pseudo-random generator good enough for
cryptographical purposes?
Basic concept: A pseudo-random generator is called cryptographically strong if the
sequence of bits it produces, from a short random seed, is so good for using with
ONE-TIME PAD cryptosystem, that no polynomial time algorithm allows a cryptanalyst
to learn any information about the plaintext from the cryptotext.
A cryptographically strong pseudo-random generator would therefore provide sufficient
security in a secret-key cryptosystem if both parties agree on some short seed and never
use it twice.
As discussed later: Cryptographically strong pseudo-random generators could provide
perfect secrecy also for public-key cryptography.
Problem: Do cryptographically strong pseudo-random generators exist?
Remark: The concept of a cryptographically strong pseudo-random generator is one of
the key concepts of the foundations of computing.
Indeed, a cryptographically strong pseudo-random generator exists if and only if a
one-way function exists what is equivalent with P = UP and what implies P = NP.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 15/37
Candidates for cryptographically strong pseudo-random generators
So far there are only candidates for cryptographically strong pseudo-random generators.
For example, cryptographically strong are all pseudo-random generators that are
unpredictable to the left in the sense that a cryptanalyst that knows the generator and
sees the whole generated sequence except its first bit has no better way to find out this
first bit than to toss the coin.
It has been shown that if integer factoring is intractable, then the so-called BBS
pseudo-random generator, discussed below, is unpredictable to the left.
(We make use of the fact that if factoring is unfeasible, then for almost all quadratic
residues x mod n, coin-tossing is the best possible way to estimate the least significant
bit of x after seeing x2 mod n.)
Let n be a Blum integer. Choose a random quadratic residue x0 (modulo n).
For i ≥ 0 let
xi+1 = xi
2
mod n, bi = the least significant bit of xI
For each integer i, let
BBS n,i (x0) = b0 . . . bi−1
be the first i bits of the pseudo-random sequence generated from the seed x0 by the BBS
pseudo-random generator.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 16/37
BBS pseudo-random generator — analysis
Choose random x, relatively prime to n, compute x0 = x2
mod n
xi+1 = xi
2
mod n, bi = the least significant bit of xI
BBSn,i (x0) = b0 . . . bi−1
Assume that the pseudo-random generator BBS with a Blum integer is not unpredictable
to the left.
Let y be a quadratic residue from Zn
∗
.
Compute BBSn,I−1(y) for some i > 1.
Let us pretend that last (i − 1) bits of BBSn,i (x) are actually the first (i − 1) bits of
BBSn,I−1(y), where x is the principal square root of y.
Hence, if the BBS pseudo-random generator is not unpredictable to the left, then there
exists a better method than coin-tossing to determine the least significant bit of x, what
is, as mentioned above, impossible.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 17/37
Randomized encryptions
From security point of view, public-key cryptography with deterministic encryptions has
the following serious drawback:
A cryptoanalyst who knows the public encryption function e k and a cryptotext c can try
to guess a plaintext w, compute e k (w) and compare it with c.
The purpose of randomized encryptions is to encrypt messages, using randomized
algorithms, in such a way that one can prove that no feasible computation on the
cryptotext can provide any information whatsoever about the corresponding plaintext
(except with a negligible probability).
Formal setting: Given: plaintext-space P
cryptotext C
key-space K
random-space R
encryption: e k : P x R → C
decryption: d k : C → P or C → 2P
such that for any p, r:
d k (e k (p, r)) = p.
d k , e k should be easy to compute.
Given e k , it should be unfeasible to determine d k .
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 18/37
Secure encryption – First definition
Definition – semantic security of encryption A cryptographic system is semantically
secure if for every feasible algorithm A, there exists a feasible algorithm B so that for
every two functions
f , h : {0, 1}∗
→ {0, 1}n
and all probability ensembles {X n}n∈N , where X n ranges over {0, 1}n
Pr[A(E(Xn), h(Xn)) = f (Xn)] < Pr[B(h(Xn)) = f (Xn)] + µ(n),
where µ is a negligible function.
It can be shown that any semantically secure public-key cryptosystem must use a
randomized encryption algorithm.
RSA cryptosystem is not secure in the above sense. However, randomized versions of
RSA are semantically secure.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 19/37
Secure encryptions – Second definition
Definition A randomized-encryption cryptosystem is polynomial time secure if, for any c
∈ N and sufficiently large s ∈ N (security parameter), any randomized polynomial time
algorithms that takes as input s (in unary) and the public key, cannot distinguish between
randomized encryptions, by that key, of two given messages of length c, with the
probability larger than 1
2
+ 1
sc .
Both definitions are equivalent.
Example of a polynomial-time secure randomized (Bloom-Goldwasser) encryption:
p, q - large Blum primes n = p × q - key
Plaintext-space - all binary strings
Random-space – QRn
Crypto-space - QRn × {0, 1}∗
Encryption: Let w be a t-bit plaintext and x0 a random quadratic residue modulo n.
Compute xt and BBSn,t (x0) using the recurrence
xi+1 = x2
i mod n
Cryptotext: (xt , w ⊕ BBSn,t (x0))
Decryption: Legal user, knowing p, q, can compute x0 from xt , then BBSn,t (x0), and
finally w.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 20/37
HASH FUNCTIONS
Another very simple, fundamental and important cryptographic concept is that of hash
functions.
Hash functions
h : {0, 1}∗
→ {0, 1}m
; h : {0, 1}n
→ {0, 1}m
, n >> m
map (very) long messages w into short ones, called usually messages digests or hashes or
fingerprints of w, in a way that has important cryptographic properties.
Digital signatures are one of important applications of hash functions.
In most of the digital signature schemes, to be discussed in the next chapter, the length
of a signature is at least as long as of the message being signed. This is clearly a big
disadvantage.
To remedy this situation, signing procedure is applied to a hash of the message, rather
than to the message itself. This is OK provided the hash function has good
cryptographic properties, discussed next.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 21/37
PROPERTIES HASH FUNCTIONS SHOULD HAVE I.
We now derive basic properties cryptographically good hash functions
should have by analysing several possible attacks on their use.
Attack 1 If Eve gets a valid signature (w,y), where y = sigk(h(w)) and she
would be able to find w’ such that h(w’)=h(w), then also (w’,y), a forgery,
would be a valid signature.
Cryptographically good hash function should therefore have the following
weak collision-free property
Definition 1. Let w be a message. A hash function h is weakly collision-free
for w, if it is computationally infeasible to find a w’ such that h(w)=h(w’).
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 22/37
PROPERTIES HASH FUNCTIONS SHOULD HAVE II.
Attack 2 If Eve finds two w and w’ such that h(w’)=h(w), she can ask Alice
to sign h(w) to get signature s and then Eve can create a forgery (w’,s).
Cryptographically good hash function should therefore have the following
strong collision-free property
Definition 2. A hash function h is strongly collision-free if it is
computationally infeasible to find two elements w = w such that
h(w)=h(w’).
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 23/37
PROPERTIES HASH FUNCTIONS SHOULD HAVE III.
Attack 3 If Eve can compute signature s of a random z, and then she can
find w such that z=h(w), then Eve can create forgery (w,s).
To exclude such an attack, hash functions should have the following
one-wayness property.
Definition 3. A hash function h is one-way if it is computationally infeasible
to find, given z, an w such that h(w)=z.
One can show that if a hash function has strongly collision-free property,
then it has one-wayness property.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 24/37
Hash functions and integrity of data
An important use of hash functions is to protect integrity of data in the
following way:
The problem of protecting data of arbitrary length is reduced, using hash
functions, to the problem to protect integrity of the data of fixed (and
small) length – of their fingerprints.
In addition, to send reliably a message w through an unreliable (and cheap)
channel, one sends also its (small) hash h(w) through a very secure (and
therefore expensive) channel.
The receiver, familiar also with the hash function h that is being used, can
then verify the integrity of the message w’ he receives by computing h(w’)
and comparing
h(w) and h(w’) .
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 25/37
EXAMPLES
Example 1 For a vector a = (a1, . . . , ak ) of integers let
H(a) =
kX
i=0
ai mod n
where n is a product of two large integers.
This hash functions does not meet any of the three properties mentioned on the last slide.
Example 2 For a vector a = (a1, . . . , ak ) of integers let
H(a) = (
kX
i=0
ai )2
mod n
This fuction is one-way, but it is not weakly collision-free.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 26/37
FINDING COLLISIONS with INVERSION ALGORITHM
Theorem Let h : X → Z be a hash function where X and Z are finite and |X| ≥ 2|Z|. If
there is an inversion algorithm A for h, then there exists randomized algorithm to find
collisions.
Sketch of the proof. One can easily show that the following algorithm
1 Choose a random x ∈ X and compute z=h(x); Compute x1 = A(z);
2 if x1 = x, then x1 and x collide (under h – success) else failure
has probability of success
p(success) =
1
|X|
X
x∈X
|[x]| − 1
|[x]|
≥
1
2
where, for x ∈ X, [x] is the set of elements having the same hash as x.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 27/37
VARIATION on BIRTHDAY PARADOX
It is well known that if there are 23 (39) [40] people in one room, then the
probability that two of them have the same birthday is more than 50%
(70%)[89%] — this is called a Birthday paradox.
More generally, if we have n objects and r people, each choosing one object
(so that several people can choose the same object), then if
r ≈ 1.177
√
n(r ≈
√
2λ), then probability that two people choose the same
object is 50% ((1 − e−λ)%).
Another version of the birthday paradox: Let us have n objects and two
groups of r people. If r ≈
√
λn, then probability that someone from one
group chooses the same object as someone from the other group is
(1 − e−λ).
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 28/37
Birthday Paradox attack on digital signatures
Assume Alice uses a hash function that produces 50 bits.
Fred, who wants Alice to sign a fraudulent contract, find 30 places in a
good document, where he can make change in the document (adding a
coma, space, . . . ) such that Alice would not notice that. By choosing at
each place whether to make or not a change, he can produce 230
documents essentially identical with the original good document.
Similarly, Fred makes 230 changes of the fraudulent document.
Considering birthday problem with n = 250, r = 230 we get that r =
√
λn,
with λ = 210 and therefore with probability 1 − e−1024 ≈ 1 there is a
version of the good document that has the same hash as a version of the
fraudulent document.
Finding a match, Fred can ask Alice to sign a good version and then
append the signature to the fraudulent contract.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 29/37
HASH FUNCTION DOMAIN LOWER BOUND
Birthday paradox imposes a lower bound on the sizes of message digests
(fingerprints)
For example a 40-bit message would be insecure because a collision could
be found with probability 0.5 with just over 2020 random hashes.
Minimum acceptable size of message digest seems to be 128 and therefore
160 are used in such important systems as DSS – Digital Signature
Schemes (standard).
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 30/37
AN ALMOST GOOD HASH FUNCTION
We show an example of the hash function (so called Discrete Log Hash Function) that
seems to have as the only drawback that it is too slow to be used in practice:
Let p be a large prime such that q = (p−1)
2
is also prime and let α, β be two primitive
roots modulo p. Denote a = logα β (that is β = αa
).
h will map two integers smaller than q to an integer smaller than p, for
m = x0 + x1q, 0 ≤ x0, x1 ≤ q − 1 as follows,
h(x0, x1) = h(m) = αx0
βx1
(mod p).
To show that h is one-way and collision-free the following fact can be used:
FACT: If we know different messages m1 and m2 such that h(m1) = h(m2), then we can
compute logα β.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 31/37
EXTENDING HASH FUNCTIONS
Let h : {0, 1}m
→ {0, 1}t
be a strongly collision-free hash function, where m > t + 1.
We design now a strongly collision-free hash function
h∗
:
∞X
i=m
{0, 1}i
→ {0, 1}t
.
Let a bit string x, |x| = n > m, have decomposition
x = x1 x2 . . . xk ,
where |xi | = m − t − 1 if i < k and |xk | = m − t − 1 − d for some d. (Hence
k =
l n
(m − t − 1)
m
.)
h∗
will be computed as follows:
1 for i=1 to k-1 do yi := xi ;
2 yk := xk 0d
; yk+1 := binary representation of d ;
3 g1 := h(0t+1
y1) ;
4 for i=1 to k do gi+1 := h(gi 1 yi+1) ;
5 h∗
(x) := gk+1.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 32/37
HASH FUNCTIONS from CRYPTOSYSTEMS
Let us have computationally secure cryptosystem with plaintexts, keys and cryptotexts
being binary strings of a fixed length n and with encryption function ek .
If
x = x1 x2 . . . xk
is decomposition of x into substrings of length n, g0 is a random string, and
gi = f (xi , gi−1)
for i = 1, . . . , k, where f is a function that “incorporates” encryption function ek of the
cryptosystem, then
h(x) = gk .
For example such good properties have these two functions:
f (xi , gi−1) = egi−1 (xi ) ⊕ xi
f (xi , gi−1) = egi−1 (xi ) ⊕ xi ⊕ gi−1
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 33/37
PRACTICALLY USED HASH FUNCTIONS
A variety of hash functions has been constructed. Very often used hash
functions are MD4, MD5 (created by Rivest in 1990 and 1991 and
producing 128 bit message digest).
NIST even published, as a standard, in 1993, SHA (Secure Hash
Algorithm) – producing 160 bit message digest – based on similar ideas as
MD4 and MD5.
A hash function is called secure if it is strongly collision-free.
One of the most important cryptographic results of the last years was due
to the Chinese Wang who has shown that MD4 is not cryptographically
secure.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 34/37
Randomized version of RSA-like cryptosystems
The scheme works for any trapdoor function (as in case of RSA),
f : D → D, D ⊂ {0, 1}n
,
for any pseudorandom generator
G : {0, 1}k
→ {0, 1}l
, k << l
and any hash function
h : {0, 1}l
→ {0, 1}k
,
where n = l + k. Given a random seed s ∈ {0, 1}k
as input, G generates a pseudorandom
bit-sequence of length l.
Encryption of a message m ∈ {0, 1}l
is done as follows:
1 A random string r ∈ {0, 1}k
is chosen.
2 Set x = (m ⊕ G(r)) (r ⊕ h(m ⊕ G(r))). (If x /∈ D go to step 1.)
3 Compute encryption c = f(x) – length of x and of c is n.
Decryption of a cryptotext c.
Compute f −1
(c) = a b, |a| = l and |b| = k.
Set r = h(a) ⊕ b and get m = a ⊕ G(r).
Comment Operation ” ” stands for a concatenation of strings.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 35/37
Bloom-Goldwasser cryptosystem once more
Private key: Blum primes p and q.
Public key: n = pq.
Encryption of x ∈ {0, 1}m
.
1 Randomly choose s0 ∈ {0, 1, . . . , n}.
2 For I = 1, 2, . . . , m + 1 compute
si ← s2
i−1 mod n
and σi = lsb(si ).
The cryptotext is (sm+1, y), where y = x ⊕ σ1σ2 . . . σm.
Decryption: of the cryptotext (r, y):
Let d = 2−m
mod φ(n)).
Let s1 = rd
mod n.
For i = 1, . . . , m, compute σi = lsb(si ) and si+1 ← s2
i mod n
The plaintext x can then be computed as y ⊕ σ1σ2 . . . σm.
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 36/37
Global goals of cryptography
Cryptosystems and encryption/decryption techniques are only one part of modern
cryptography.
General goal of modern cryptography is construction of schemes which are robust against
malicious attempts to make these schemes to deviate from their prescribed functionality.
The fact that an adversary can design its attacks after the cryptographic scheme has
been specified, makes design of such cryptographic schemes very difficult – schemes
should be secure under all possible attacks.
In the next chapters several of such most important basic functionalities and design of
secure systems for them will be considered. For example: digital signatures, user and
message authentication,. . .
Moreover, also such basic primitives as zero-knowledge proofs, needed to deal with
general cryptography problems will be presented and discussed.
We will also discuss cryptographic protocols for a variety of important applications. For
example for voting, digital cash,. . .
prof. Jozef Gruska IV054 6. Public-key cryptosystems, II. Other cryptosystems, security, PRG, hash functions 37/37