Cours.Frey
124
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
124
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Publié par
Langue
English
Mathematical Background
of Public Key Cryptography
Gerhard Frey
University of Duisburg-Essen
Institute for Experimental
Mathematics
frey@exp-math.uni-essen.de
G.A.T.I
CIRM -May 12-16, 2003
11 Data security and Arithmetic
Problem:
¡¡!A open B
"
C
(A;m;B) 7! (B;m;A)
The transfer of the message has to be
“secure”.
This has (at least) 3 aspects:
2†Reliability (engineers)
†Correctness(codingtheory,engineers
and mathematicians)
†Authenticity,privateness(cryptogra-
phy,mathematicians,computerscien-
tists, engineers)
Solutionshavetobesimple,efficientand
cheap!
3There was a basic decision some sixty
years ago:
Messages are stored and transmitted as
numbers.
This makes it possible to apply
Arithmetic
to data security.
4Weshallconcentratetothethirdaspect
which uses
ENCRYPTION
provided bycryptography.
This is, in the true sense of the word, a
classic discipline:
We find it in Mesopotamia and Caesar
used it.
5Encryption Devices
6The devices shown are examples for
symmetric procedures:
There is a common secret amongst the
partners which enables them to de- and
encrypt.
In principle they are used till today, in
refined versions.
The new standard is called AES.
Typicallythehistoricalexamplesarein-
volving secret services and military and
theinformationisexchangedamongsta
community in which each member is to
be trusted.
7This has changed dramatically becau-
seofelectroniccommunicationinpublic
networks.
So data security has become a public
challenge.Therearemillionsofpartners
in nets.
Key exchange necessary for symmetric
systemscannotberelyonpersonaltrust
and communication.
8Solution:
PUBLIC KEY CRYPTOSYSTEMS
( Diffie-Hellman 1976)
EachmemberAofthenetworkhastwo
keys:
†a private key s produced by him-A
self never leaving the private secure
environment
†a public keyp published in a direc-A
tory.
p is related to s by a (known)A A
One-Way function.
Forkeyexchangeandforencryption/decryption
A uses both keys (and the public keyof
the partner B if necessary).
There is no practically useable leakage
of information about s ; s !A B
9BASIC IDEA:
One Way Functions
(Informal)Definition:
Let A and B be two finite sets of num-
bers and f a map from A to B.
f is a one way function if a computer
can calculate f(a) in• 50 ms
¡30butwithveryhighprobability(1¡10 )
it is impossible to find for given value
f(a) the argument a during the next
1000 years by using all known methods
and all existing computers.
10
