Search for notes by fellow students, in your own course and all over the country.
Browse our notes for titles which look like what you need, you can preview any of the notes via a sample of the contents. After you're happy these are the notes you're after simply pop them into your shopping cart.
Document Preview
Extracts from the notes are below, to see the PDF you'll receive please use the links above
PRINCIPLES OF PUBLIC KEY CRYPTOGRAPHY
The concept of public key cryptography evolved from an attempt to
attack two of the most difficult problems associated with symmetric
encryption
...
Digital signatures
...
These algorithms have the following
important characteristics:
It is computationally infeasible to determine the decryption key given
only the knowledge of the cryptographic algorithm and the encryption
key
...
The essential steps are the following:
Each user generates a pair of keys to be used for encryption and
decryption of messages
...
This is the public key
...
Powered By www
...
com
If A wishes to send a confidential message to B, A encrypts the
message using B’s public key
...
No
other recipient can decrypt the message because only B knows B’s
private key
...
As long as a system controls its private key, its incoming
communication is secure
...
Suppose A wishes to send a message to B
...
KRb is
known only to B, whereas KUb is publicly available and therefore accessible
by A
...
i
...
, Y=E KUb(X)
The receiver can decrypt it using the private key KRb
...
e
...
technoscriptz
...
Plain text
Encryption
Sender’s
private key
Decryption
Cipher
text
Sender’s
public key
Fig: authentication
The encrypted message serves as a digital signature
...
There is no protection of confidentiality because
any observer can decrypt the message by using the sender’s public key
...
Ciphertext Z = EKUb [EKRa (X)]
Powered By www
...
com
Plaintext X = EKUa[EKRb (Y)]
Initially, the message is encrypted using the sender’s private key
...
Next, we encrypt again, using the receiver’s
public key
...
Thus confidentiality is
provided
...
It is computationally easy for a sender A, knowing the public key and
the message to be encrypted M, to generate the corresponding
ciphertext: C=EKUb(M)
...
It is computationally infeasible for an opponent, knowing the public
key KUb, and a ciphertext C, to recover the original message M
...
The counter measure is to use large keys
...
technoscriptz
...
This algorithm
makes use of an expression with exponentials
...
That
is, the block size must be less than or equal to log 2 (n); in practice, the block
size is k-bits, where 2k < n < 2k+1
...
the sender knows
the value of e and only the receiver knows the value of d
...
For this algorithm to be satisfactory for public
key encryption, the following requirements must be met:
It is possible to find values of e, d, n such that M ed = M mod n for all
M
It is infeasible to determine d given e and n
...
We need to find the relationship of the
form:
Med = M mod n
A corollary to Euler’s theorem fits the bill: Given two prime numbers p and
q and two integers, n and m, such that n=pq and 0
Powered By www
...
com
mkФ(n) +1 = mk(p-1)(q-1) +1 = m mod n
where Ф(n) – Euler totient function, which is the number of positive integers
less than n and relatively prime to n
...
According to the rule
of modular arithmetic, this is true only if d (and therefore e) is relatively
prime to Ф(n)
...
The steps involved in RSA algorithm for generating the key are
Select two prime numbers, p = 17 and q = 11
...
Select e such that e is relatively prime to Ф(n) = 160 and less than
Ф(n); we choose e = 7
...
the correct value
is d = 23, because 23*7 = 161 = 1 mod 160
...
Key Generation
Select p, q
p ,q both prime pq
Calculate n = p x q
Calculate (n) = (p -l)(q - 1)
Select integer e
gcd((n), e) = 1; 1< e< (n)
Calculate
d= e-1mod (n)
d
Powered By www
...
com
Public key
KU = { e,n}
Private key
KR = {d,n}
Encryption
Plaintext
M
Ciphertext
C = Me (mod n)
Decryption
Ciphertext
Plaintext
C
M = Cd (mod n)
Decryption
Plaint
Cipher
ext
text 11
88
KU = 7,187
KR = 23, 187
Figure : Example of RSA
Algorithm
Security of RSA
There are three approaches to attack the RSA:
brute force key search (infeasible given size of numbers)
mathematical attacks (based on difficulty of computing ø(N), by
factoring modulus N)
Powered By www
...
com
timing attacks (on running time of decryption)
Factoring Problem
Mathematical approach takes 3 forms:
Factor n = p*q, hence find Ф(n) and then d
...
Find d directly, without first determination Ф(n)
...
Although
the timing attack is a serious threat, there are simple countermeasures that
can be used:
Constant exponentiation time – ensures that all exponentiations take
the same amount of time before returning a result
...
Blinding – multiply the ciphertext by a random number before
performing exponentiation
...
technoscriptz
...
Append PGP keys to email messages or post to news groups or
email list
• Major weakness is forgery
o Anyone can create a key claiming to be someone else and
broadcast it
o Until forgery is discovered can masquerade as claimed user
Publicly Available Directory
• Can obtain greater security by registering keys with a public directory
• Directory must be trusted with properties:
o Contains {name, public-key} entries
o Participants register securely with directory
o Participants can replace key at any time
o Directory is periodically published
o Directory can be accessed electronically
• Still vulnerable to tampering or forgery
Powered By www
...
com
Public-Key Authority
• Improve security by tightening control over distribution of keys from
directory
• Has properties of directory
• Requires users to know public key for the directory
• Users interact with directory to obtain any desired public key securely
o Does require real-time access to directory when keys are needed
Public-Key Certificates
• Certificates allow key exchange without real-time access to public-key
authority
• A certificate binds identity to public key
o Usually with other info such as period of validity, rights of use etc
• With all contents signed by a trusted Public-Key or Certificate Authority
(CA)
Powered By www
...
com
• Can be verified by anyone who knows the public-key authorities publickey
Powered By www
...
com
DIFFIE-HELLMAN KEY EXCHANGE
The purpose of the algorithm is to enable two users to exchange a key
securely that can then be used for subsequent encryption of messages
...
First, we define a primitive root of a prime
number p as one whose power generate all the integers from 1 to (p-1) i
...
, if
‘a’ is a primitive root of a prime number p, then the numbers
a mod p, a2 mod p, … ap-1 mod p
are distinct and consists of integers from 1 to (p-1) in some permutation
...
With this background,
we can define Diffie Hellman key exchange as follows:
There are publicly known numbers: a prime number ‘q’ and an integer α that
is primitive root of q
...
User A
selects a random integer XA < q and computes YA = α
XA
mod q
...
Each side keeps the X value private and makes the Y value
available publicly to the other side
...
Powered By www
...
com
K = (YB)XA mod q
= (α XB mod q)XA mod q
= (α XB)XA mod q
= (α XA)XB mod q
= (α XA mod q)XB mod q
= (YA)XB mod q
The result is that two sides have exchanged a secret key
...
For large primes, the latter task is considered infeasible
...
technoscriptz
...
Suppose Alice and Bob wish to exchange keys, and Darth is the
adversary
...
Darth prepares for the attack by generating two random private keys
XD1 and XD2 and then computing the corresponding public keys YD1
and YD2
...
Alice transmits YA to Bob
...
Darth intercepts YA and transmits YD1 to Bob
...
4
...
5
...
6
...
Darth calculates K1 =
(YB)XD1 mod q
...
Alice receives YD2 and calculates K2 = (YD2)XA mod q
...
All future communication between Bob and Alice is compromised in the
following way:
1
...
2
...
3
...
In
the first case, Darth simply wants to eavesdrop on the communication
without altering it
...
The key exchange protocol is vulnerable to such an attack because it does
not authenticate the participants
...
Powered By www
...
com
Elliptic Curve Cryptography
The addition operation in ECC is the counterpart of modular multiplication
in RSA, and multiple addition is the counterpart of modular exponentiation
...
Consider the equation Q = kP where Q, P in Ep(a, b) and k < p
...
This is called the discrete logarithm problem for
elliptic curves
...
In a real application, k would be so large as to make the
brute-force approach infeasible
...
First pick a large integer q, which is either a prime number p or an integer of
the form 2m and elliptic curve parameters a and b
...
Next, pick a base point G = (x1, y1) in Ep(a, b)
whose order is a very large value n
...
Eq(a, b) and G are
parameters of the cryptosystem known to all participants
...
technoscriptz
...
A selects an integer nA less than n
...
A then
generates a public key PA = nA x G; the public key is a point in Eq(a,
b)
...
B similarly selects a private key nB and computes a public key PB
...
A generates the secret key K = nA x PB
...
Powered By www
...
com