Tổng quan về mật mã học
Huỳnh Trọng Thưa



Introduction
• Cryptography was used as a
tool to protect national
secrets and strategies.
• 1960s (computers and
communications systems) ->
means to protect information
and to provide security
services.
2


Introduction (cont.)
• 1970s: DES (Feistel, IBM) - the most well-known
cryptographic mechanism in history
• 1976: public-key cryptography (Diffie and
Hellman)
• 1978: RSA (Rivest et al.) - first practical public-key
encryption and signature scheme
• 1991: the first international standard for digital
signatures (ISO/IEC 9796) was adopted.
3


Information security and
cryptography

• Some information security objectives
–
–
–
–
–
–
–
–

Privacy or confidentiality
Data integrity
Entity authentication or identification
Message authentication
Signature
Authorization
Validation
Access control

4


Information security and
cryptography (cont.)
• Some information security objectives
–
–
–
–
–

–
–
–
–

Certification
Timestamping
Witnessing
Receipt
Confirmation
Ownership
Anonymity
non-repudiation
Revocation
5


Information security and
cryptography (cont.)
• Cryptography is the study of mathematical
techniques related to aspects of information
security such as confidentiality, data integrity,
entity authentication, and data origin
authentication.
• Cryptography is not the only means of
providing information security, but rather one
set of techniques.
6



Cryptographic goals
•
•
•
•

Confidentiality
Data integrity
Authentication
Non-repudiation
Cryptography is about the prevention
and detection of cheating and other
malicious activities.
7


A taxonomy of
cryptographic
primitives

8


Background on functions
• Function:
 f:XY
 f(x)=y

• Ex:


f(1) = 1 f(2) = 4 f(3) = 9
f(4) = 5 f(5) = 3 f(6) = 3
f(7) = 5 f(8) = 9 f(9) = 4
f(10) = 1.

 X = {1, 2, 3,... , 10}
 f(x)= rx, where rx is the remainder
when x2 is divided by 11.
 image of f is the set Y = {1, 3, 4, 5, 9}

9


1-1 functions
• A function is 1 − 1 (injection - đơn ánh) if each
element in Y is the image of at most one
element in X
• A function is onto (tồn ánh) if each element
in Y is the image of at least one element in X,
i.e Im(f)=Y
• If a function f: X → Y is 1−1 and Im(f)=Y, then f
is called a bijection (song ánh).
10


Inverse function
• f:XY and g:YX; g(y)=x where f(x)=y
• g obtained from f, called the inverse function of f, g = f−1.

• Ex: Let X = {a, b, c, d, e}, and Y = {1, 2, 3, 4, 5}


11


One-way functions
• A function f from a set X to a set Y is called a
one-way function if f(x) is “easy” to compute
for all x ∈ X but for “essentially all” elements y
∈ Im(f) it is “computationally infeasible” to
find any x ∈ X such that f(x)= y.
– Ex: X = {1, 2, 3,... , 16}, f(x)= rx for all x ∈ X where rx
is the remainder when 3x is divided by 17.

12


Permutations
(Hốn vị)

• Let S be a finite set of elements.
– A permutation p on S is a bijection from S to itself
(i.e., p: S→S).

• Ex: S = {1, 2, 3, 4, 5}. A permutation p: S→S is
defined as follows:
p(1) = 3,p(2) = 5,p(3) = 4,p(4) = 2,p(5) = 1.

13



Involutions
(Ánh xạ đồng phơi)

• Let S be a finite set and let f be a bijection
from S to S (i.e., f : S→S).
 The function f is called an involution if f = f−1.
 f(f(x)) = x for all x ∈S.

14


Basic terminology and concepts
• M denotes a set called the message space.
– An element of M is called a plaintext message
– Ex: M may consist of binary strings, English text, computer
code, etc.

• C denotes a set called the ciphertext space.
– C consists of strings of symbols from an alphabet of
definition, which may differ from the alphabet of definition
for M.
– An element of C is called a ciphertext.

15


Encrypt and decrypt transformations
(Các phép biến đổi)
• K denotes a set called the key space. An element of K
is called a key.

• Each element e ∈ K uniquely determines a bijection
from M to C, denoted by Ee.
• Ee is called an encryption function or an encryption
transformation
• For each d ∈ K, Dd denotes a bijection from C to M
(i.e., Dd : C→M). Dd is called a decryption function or
decryption transformation.
16


Encrypt and decrypt transformations
(cont.)
• Ee : e ∈ K ; Dd : d ∈ K
– for each e ∈ K there is a unique key d ∈ K such that Dd = Ee-1;
– that is, Dd(Ee(m)) = m for all m ∈ M.

• The keys e and d in the preceding definition are referred to as a
key pair and some times denoted by (e, d).
• To construct an encryption scheme requires one to select
–
–
–
–

a message space M,
a ciphertext space C,
a key space K,
a set of {Ee : e ∈ K}, and a corresponding set of {Dd:d ∈ K}.

17



Ex of encryption scheme
• Let M = {m1,m2,m3} and C = {c1,c2,c3}.
– There are precisely 3! = 6 bijections from M to C.
– The key space K = {1, 2, 3, 4, 5, 6} has six elements in it,
each specifying one of the transformations.

18


Communication participants

• Entity or party: sender, receiver, adversary
19


Channels
• A channel is a means of conveying information from
one entity to another.
• An unsecured channel is one from which parties
other than those for which the information is
intended can reorder, delete, insert, or read.
• A secured channel is one from which an adversary
does not have the ability to reorder, delete, insert, or
read.

20



Security
• A fundamental premise in cryptography is that
the sets M, C,K, {Ee : e ∈ K}, {Dd : d ∈ K} are
public knowledge.
• When two parties wish to communicate
securely using an encryption scheme, the only
thing that they keep secret is the particular
key pair (e, d) which they are using, and which
they must select.
21


Security (cont.)
• An encryption scheme is said to be breakable
if a third party, without prior knowledge of the
key pair (e, d), can systematically recover
plaintext from corresponding ciphertext
within some appropriate time frame.
• The number of keys (i.e., the size of the key
space) should be large enough to make this
approach computationally infeasible.
22


Cryptology
• Cryptanalysis is the study of mathematical techniques
for attempting to defeat cryptographic techniques,
and, more generally, information security services.
• A cryptanalyst is someone who engages in
cryptanalysis.

• Cryptology is the study of cryptography and
cryptanalysis.
• Cryptographic techniques are typically divided into two
generic types: symmetric-key and public-key.

23


Symmetric-key encryption
• Block ciphers
• Stream ciphers

24


Overview of block ciphers and
stream ciphers
• Let {Ee : e ∈K} and {Dd : d ∈K}, K is the key space.
– The encryption scheme is said to be symmetric-key if for
each associated encryption/decryption key pair (e, d), it is
computationally “easy” to determine d knowing only e,
and to determine e from d.

• Since e = d in most practical symmetric-key
encryption schemes, the term symmetric-key
becomes appropriate.
• Other terms used in the literature are single-key,
one-key, private-key, and conventional encryption.
25