Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

1/ Introduction to cryptography
•
•
•
•
•
•

Common terms used in cryptography
Properties of secure communication
Simple substitution ciphers
Divisibility and greatest common divisors
Modular arithmetic
Elliptic curve arithmetic

A) DEFINITIONS AND BASIC PRINCIPLES

DEFINITIONS AND BASIC PRINCIPLES

DEFINITIONS AND BASIC PRINCIPLES

CRYPTANALYSIS

B) Properties of Secure
Communication
• Authentication
❖Service assures that the two communicating
entities are authentic (genuine)
❖Service assures that the connection is not
interfered with by another connection in such
a way that a third party can masquerade as
one of the two legitimate parties for the
purposes of unauthorized transmission or
reception of sensitive information

Properties of Secure Communication
• Confidentiality
Service assures that the information in a
computer system as well as the transmitted
information be accessible only for reading by
authorized parties
...
Integrity is
therefore the protection of information
applications, systems, and networks from
intentional, unauthorized, or accidental changes

Properties of Secure Communication
• Non-repudiation
Service guarantees that neither the sender of a
message can deny the transmission of the
message nor the receiver of a message is able to
deny the reception of the message

C/ SUBSTITUTION CIPHERS
• A simple substitution cipher is the Caesar
cipher which Julius Caesar used during his
campaigns
...

• Let the key = 5 cyclic shifts
• Consider a ciphertext sent by Caesar as
follows:

SUBSTITUTION CIPHERS
• To decrypt the message sent, simply take each
letter in the message and shift it five letters up
the alphabet
...

• The second line is the decrypted plaintext and
it reads
Enemy falling back
...
Lucius

SUBSTITUTION CIPHERS
• This is a simple monoalphabetic substitution
cipher where each character in an alphabet is
replaced by another alphabet or sometimes
even by a symbol of a different alphabet
...
g y is wrapped-around to d
...
"

D) Divisibilty and Greatest
Common Divisor (GCD)
a) Divisibilty
b) GCD

a) Divisibility and GCD
• Let a, m, r be integers such that 0  r < m
...
By performing the
division of a by m denoted as a  m we can write
[a  m]  a  m
or
0  a - m [a  m]
believing that an integer, r exists for which we can replace the
inequality, above equation can be written as
a = m [a  m] + r
r is called the residue of a modulo m
...
For r > 0, divisibility implies that m 
(a – r)
...
The greatest common divisor, d of
two integers a and b has the following properties:
• d0
(d is non negative)
• d a and d b (d is a common divisor of a and b)
• e a and e b implies e d (every common
divisor divides d)

GCD
• The number d is denoted by gcd (a, b)
...

For example
gcd (15, 10) = 5
gcd (18, 10) = 2
gcd (21, 10) = 1
• 21 and 10 in the example above are relatively prime
...


PRIME NUMBERS < 355

E) Modular arithmetic
a) Multiplicative inverse
b) Euler totient function

a) Multiplicative inverse
• Let Zn denote the set of nonnegative integers
less than n: Zn = {0, 1, - - - , (n – 1)}
• Every element x in Zn has additive inverse, that
is, for each x  Zn there is a y  Zn such that
x + y mod n = 0
...

• A multiplicative inverse of x is an element z-1 
Zn such that x x-1  1 mod n
...
For example, 3 does
not have a multiplicative inverse in Z9
...

• It can therefore be concluded that an element x >
0 of Zn has a multiplicative inverse in Zn if and
only if gcd (x, n) = 1, that is, either x =1 or x does
not divide n

Multiplicative inverse

From Table 1, n = 11 is prime implying every element x  0 of
Z11 has a multiplicative inverse in Z11 except 0
...
Some elements x  0
of Z9, namely 3 and 6 do not have multiplicative inverses in Z9
since they are not relatively prime with respect to n = 9
...
Example, for n = 7, the positive integers not
exceeding 7 are 1, 2, 3, 4, 5, 6, 7
...
The number of situations where the
equality is satisfied is 6, i
...
Therefore (7) is 6
...


Elliptic curve arithmetic

GENERAL SHAPE

EXAMPLE CON’T – NEUTRAL
ELEMENTS
• P = (a, b) and P’ = (a, -b)
• No third point of intersection, R exist, that is
point exist at infinity

NEUTRAL AND INVERSE ELEMENTS

POINT DOUBLING – adding a point to
itself

POINT ITERATION – adding a point k-1
times to itself

Mathematical Description of
Geometrical Transform

Mathematical Description of
Geometrical Transform

HOW CAN GEOMETRY BE USEFUL TO
CRYPTOGRAPHY

ELLIPTIC CURVES AND FINITE FIELDS
• Let E: Y2 = X3 + 3X + 8 mod 13
• We look at points on E with coordinates in
finite field such that for X values the quantity
X3 + 3X + 8 is a square modulo 13
...
Complete list will give

ELLIPTIC CURVES – ADDITION IN FINITE
FIELDS
• P = (9, 7) and Q = (1, 8)
• P + Q mod 13
• The slope,  is given as
• Note that the additive inverse of -8 = 5 and
the multiplicative inverse of 1/5 = 5-1 = 8 in
mod 13 arithmetic

ELLIPTIC CURVES – ADDITION IN FINITE
FIELDS
• Using the addition theorem in finite field we
have

• Answer is in mod 13

ELLIPTIC CURVES – ADDITION IN FINITE
FIELDS
• Adding P = (9, 7) to itself

EXAMPLE CON’T – COMPLETE
ADDITION TABLE



---