Cryptography and Cryptanalysis in the Digital Age


Facharbeit (Schule), 2013
28 Seiten, Note: 1,0

Leseprobe

Englischsprachige Facharbeit
"Cryptography and Cryptanalysis
in the Digital Age"
Jan Toennemann
26. Februar 2013

CONTENTS
1
Introduction
1
2
Preliminaries
2
2.1
XOR
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2.2
Sets
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2.3
Functions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2.4
Randomness
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2.4.1
Random Variables
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2.4.2
Randomized Algorithms
. . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.5
Pseudo-Randomness
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.5.1
Pseudo-Randomness
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.5.2
Pseudo-Random Generator
. . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.5.3
Unpredictability
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.5.4
Pseudo-Random Functions
. . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.5.5
Pseudo-Random Permutations
. . . . . . . . . . . . . . . . . . . . . . . .
3
2.6
Modular Arithmetic
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.6.1
Modular Arithmetic
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.6.2
Greatest Common Divisor
. . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.6.3
Modular Inversion
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.6.4
Generators
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.6.5
Modular e'th Roots
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.6.6
Square Roots (e'th Roots with e=2)
. . . . . . . . . . . . . . . . . . . .
5
2.6.7
Discrete Logarithm
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.6.8
Trapdoor Functions
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
3
Stream Ciphers
6
3.1
General
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
3.2
The One-Time Pad
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
3.2.1
The One-Time Pad
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
3.2.2
Using the OTP As a Stream Cipher
. . . . . . . . . . . . . . . . . . . . .
6
3.2.3
Main Flaw of the OTP
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
3.3
Salsa20
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
3.3.1
Salsa20
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
3.3.2
Parallel Computing
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
i

4
Block Ciphers
9
4.1
General
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
4.2
Data Encryption Standard
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
4.2.1
Data Encryption Standard
. . . . . . . . . . . . . . . . . . . . . . . . . .
9
4.2.2
DES Core - the Feistel Network
. . . . . . . . . . . . . . . . . . . . . . .
9
4.2.3
The Feistel Function in DES
. . . . . . . . . . . . . . . . . . . . . . . . .
10
4.2.4
Exhaustive Search Attacks
. . . . . . . . . . . . . . . . . . . . . . . . . .
11
4.2.5
Exhaustive Search Attack on DES
. . . . . . . . . . . . . . . . . . . . . .
11
4.3
Advanced Encryption Standard
. . . . . . . . . . . . . . . . . . . . . . . . . . .
12
4.3.1
Advanced Encryption Standard
. . . . . . . . . . . . . . . . . . . . . . .
12
4.3.2
The Substitution-Permutation Network
. . . . . . . . . . . . . . . . . . .
12
4.3.3
How AES Operates
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
5
Message Authentication Codes
14
5.1
General
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
5.2
Cipher-based MAC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
5.2.1
Cipher-based MAC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
5.2.2
CMAC Tag Generation
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
6
Public-Key Cryptography
16
6.1
General
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
6.2
RSA
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
6.2.1
RSA
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
6.2.2
RSA's Asymmetric Key Generation
. . . . . . . . . . . . . . . . . . . . .
17
6.2.3
Encryption and Decryption in RSA
. . . . . . . . . . . . . . . . . . . . .
17
6.2.4
Why the RSA Algorithm is a Trapdoor Function
. . . . . . . . . . . . .
17
7
Measurements
18
7.1
General
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
7.2
Results
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
7.3
Conclusion
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
Sources
I
Appendix
IV
ii

CHAPTER 1
INTRODUCTION
Nowadays, everything is tied to the Internet in some way. Tim Berners-Lee's invention, meant to
ease the communication and collaboration inside the CERN research facility, is now a dominating
part of the life of each and every one of us. Millions of people use it every day to transfer sensitive
data, like doing bank transfers or sharing company documents. If a third party could obtain
this information it would wreak havoc to the companies or individuals affected.
5
Because of this, there are security measures in place. In fact, they are used in way more areas
than previously mentioned, ensuring safe and private browsing and communication. That is
where the main subject of this paper comes in: Cryptography. Although cryptography was used
long before the Internet, for example Caesar's use of the substitution cipher or the ingenious
Enigma machine used by the Germans in World War II, it is now used all over the world.
10
Personally, I'm fascinated by technology in general, but cryptography is what intrigues me
most at the moment. Current implementations combine mathematics and computer science in a
unique way, especially the mechanics of asymmetric encryption, discussed in
section 6
, fascinate
me.
Due to the wide distribution of cryptography I will need to strictly limit the topics covered,
15
which is why I am focusing on the most frequently used implementations and a few older, simpler
ones to begin on. I also had to leave out most of the mathematical part, because proving the
security of each cipher covered in this paper would've almost doubled the page count. Because
of the technical nature of this subject I have focused on digitally published papers rather than
printed books, which in addition results in enhanced availability of the cited material.
20
1

CHAPTER 2
PRELIMINARIES
2.1
XOR
XOR (exclusive or) is a logical operation performed on two operands that results in one if
both values have opposite truth values, i.e. only one operand is true. In this paper, XOR
operations will be denoted using the
-operator. The following truth table should clarify the
XOR operation:
Input
1
Input
2
Output
(Input
1
Input
2
)
0
0
0
0
1
1
1
0
1
1
1
0
2.2
Sets
Finite sets will be denoted using {0, 1}
n
, with n being the number of elements in the set rather
5
than a power, because we are in binary context. Further on, |S| will denote the size of a set S,
although in this case it equals n.
2.3
Functions
Functions map one or multiple inputs they receive as arguments to one or multiple outputs.
They are deterministic, which means that when neither the input nor the function itself changes,
the output will stay the same. To denote functions, the notation f : X Y is used, with f
10
being the function, X the input space and Y the output space.
2.4
Randomness
2.4.1
Random Variables
A random variable X is a function X : S V with V being the set where the random variable
takes it's values. For example, with X : {0, 1}
n
{0, 1}; X(y) = lsb(y) {0, 1} (lsb is an
operation extracting the least significant bit(s) of a binary number, the bits on the far right)
2

and S being distributed uniformly, the probability of X being 0 is equal to the probability of it
being 1.
2.4.2
Randomized Algorithms
While a deterministic algorithm y A(m) always maps the point m to the point A(m), a
randomized algorithm y A(m; r) with r
R
- {0, 1}
n
( r is a random variable) maps the point m
to the output space A(m), thus resulting in multiple possible outputs for the same m depending
5
on r.
2.5
Pseudo-Randomness
2.5.1
Pseudo-Randomness
Computers generally reside to Pseudo-Random Generators to achieve random looking output
to use for various tasks rather than truly random sequences. "The reason lies in many extra
benefits provided by pseudo-random generators. [...] [O]ne often needs to repeat the exact same
sequence. With a truly random generator, one actually has to record all its outcomes: long and
10
costly. The alternative is to generate pseudo-random strings from a short seed."
1
Those seeds
play an important role in cryptography, because usually, passwords, shared secrets etc. will be
used as seeds for the pseudo-random generator.
2.5.2
Pseudo-Random Generator
A pseudo-random generator expands a short input (seed) to a large, seemingly random out-
put. Therefore, a PRG G with k as seed produces the output G(k)
k, which should be
15
indistinguishable from r
R
- {0, 1}
n
.
2.5.3
Unpredictability
For a PRG to be unpredictable, there may not be a single statistical test that can distinguish
the output of the PRG from the output of a truly random function.
2.5.4
Pseudo-Random Functions
A pseudo-random function is a function defined over (K, X, Y ) :
F : K × X Y such
that there exists an efficient algorithm to evaluate F (k, x). All output from a PRF should be
20
indistinguishable from random, regardless of the input, as long as the function itself was drawn
at random.
2.5.5
Pseudo-Random Permutations
A pseudo-random permutation is a function defined over (K, X) :
E : K × X X such that
there exists an efficient algorithm to evaluate E(k, x). The PRP E(k, ·) is one-to-one, so there
exists an effective inversion algorithm D(k, y). A PRP should be indistinguishable from a truly
25
random permutation.
1
http://www.cs.bu.edu/fac/lnd/toc/z/node24.html
3

2.6
Modular Arithmetic
2.6.1
Modular Arithmetic
"Modular arithmetic [...] is a system of arithmetic for integers, where numbers "wrap around"
after they reach a certain value - the modulus"
2
, here denoted as N . Although modular arithmetic
is often denoted using (mod n) after an equation, here we will use in Z
N
instead.
To explain modular arithmetic, the 12-hour clock is a splendid example. Basically, while a
day has 24 hours, the clock can only display the hours one to twelve. Thus, on a 12-hour clock:
5
14 2 in Z
12
; 17 5 in Z
12
; 23 11 in Z
12
with denoting a congruence relation.
2.6.2
Greatest Common Divisor
For a pair of integers a and b the greatest common divisor is denoted by gcd(a, b) = x. If we use
the integers 12 and 18 as example, we get gcd(12, 18) = 6, because both 12 and 18 are divisible
by 6, but not by any integer higher than that.
For every integer pair a, b there exists another integer pair x, y such that x × a + y × b =
10
gcd(a, b). If gcd(a, b) = 1 we say that a and b are relatively prime.
2.6.3
Modular Inversion
While inverting rational numbers is considered easy, for example the inverse of 2 being
1
2
,
inverting integers in Z
N
is considered to be very hard. To invert an element x in Z
N
we need
an element y in Z
N
such that x × y = 1 in Z
N
, in which case y = x
-1
. For example, let N be
an odd integer. Then the inverse of 2 in Z
N
is
N +1
2
, because 2 × (
N +1
2
) = N + 1 1 in Z
N
.
15
But beware, not every element in Z
N
is invertible! For an element x in Z
N
to be invertible,
gcd(x, N ) = 1 must hold. We will call the set of invertible elements in Z
N
from now on (Z
N
)
,
which basically means that (Z
N
)
= {x Z
N
: gcd(x, N ) = 1}.
2.6.4
Generators
The set of invertible elements (Z
N
)
is a cyclic group, which means that every element in (Z
N
)
can be generated from a single element g inside that group by raising g to a higher power, that
20
is there exists a g (Z
N
)
such that {g
0
, g
1
, g
2
, . . . , g
p-2
} = (Z
N
)
. Any number inside (Z
N
)
which can be used as g is then called a generator of (Z
N
)
and the set {1, g, g
2
, . . .} is called
the group generated by g, denoted as <g>. If we use N = 7 and g = 3 (Z
N
)
as an example,
<g>would be {3
0
, 3
1
, 3
2
, 3
3
, 3
4
, 3
5
} = {1, 3, 2, 6, 4, 5}.
Similar to modular inversions, one must watch out here, because not every element in (Z
N
)
25
can be used as a generator!
A shortcut to the size of the (Z
N
)
group is provided by Euler's totient function, which will
be denoted as (N ), where (N ) = |(Z
N
)
|. When using the totient function on a multiple of
two known primes, one can easy compute it using (pq) = (p - 1) × (q - 1).
2.6.5
Modular e'th Roots
With p being a prime and c, e Z
p
, x
e
c in Z
p
is called an e'th root of c. For example,
30
7
1
3
6 in Z
11
because 6
3
= 216 7 in Z
11
.
Just like previously, we must pay attention, because not every e'th root exists. To determine
the existence of an e'th root we have two options: The easiest of those would be to check if
2
http://math.wikia.com/wiki/Modular_arithmetic
4
Ende der Leseprobe aus 28 Seiten

Details

Titel
Cryptography and Cryptanalysis in the Digital Age
Note
1,0
Autor
Jahr
2013
Seiten
28
Katalognummer
V263210
ISBN (eBook)
9783656523635
ISBN (Buch)
9783656524861
Dateigröße
951 KB
Sprache
Deutsch
Anmerkungen
Ausgezeichnet mit dem Dr. Hans Riegel-Fachpreis für Mathematik von der Universität Oldenburg in Kooperation mit der Dr. Hans Riegel-Stiftung. (1. Platz, 2013)
Schlagworte
cryptography, cryptanalysis, digital
Arbeit zitieren
Jan Toennemann (Autor), 2013, Cryptography and Cryptanalysis in the Digital Age, München, GRIN Verlag, https://www.grin.com/document/263210

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Cryptography and Cryptanalysis in the Digital Age


Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden