|
|
|
Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 652-653 out of 1137
Modern Operating Systems by Herbert Bos and Andrew...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf-M ODERN O PERATING S YSTEMS
Modern Operating Systems by Herbert...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf-M ODERN O PERATING S YSTEMS
Page 652
SEC. 9.5
BASICS OF CRYPTOGRAPHY
621
E
K
E
Encryption key
Decryption key
P
P
Plaintext in
Plaintext out
Encryption
algorithm
D
K
D
Decryption
algorithm
Ciphertext
C = E(P, K
E
)
P = D(C, K
D
)
Decryption
Encryption
Figure 9-15.
Relationship between the plaintext and the ciphertext.
plaintext
ATTACK
would be transformed into the ciphertext
QZZQEA
.
The de-
cryption key tells how to get back from the ciphertext to the plaintext. In this ex-
ample, the decryption key is
KXVMCNOPHQRSZYIJADLEGWBUFT
because an
A
in the ciphertext is a
K
in the plaintext, a
B
in the ciphertext is an
X
in the plaintext,
etc.
At first glance this might appear to be a safe system because although the
cryptanalyst knows the general system (letter-for-letter substitution), he does not
know which of the 26!
≈
4
×
10
26
possible keys is in use. Nevertheless, given a sur-
prisingly small amount of ciphertext, the cipher can be broken easily. The basic at-
tack takes advantage of the statistical properties of natural languages.
In English,
for example,
e
is the most common letter, followed by
t
,
o
,
a
,
n
,
i
, etc. The most
common two-letter combinations, called
digrams
, are
th
,
in
,
er
,
re
, and so on.
Using this kind of information, breaking the cipher is easy.
Many cryptographic systems, like this one, have the property that given the en-
cryption key it is easy to find the decryption key. Such systems are called
secret-
key cryptography
or
symmetric-key cryptography
.
Although monoalphabetic
substitution ciphers are completely worthless, other symmetric key algorithms are
known and are relatively secure if the keys are long enough. For serious security,
minimally 256-bit keys should be used, giving a search space of 2
256
≈
1. 2
×
10
77
keys. Shorter keys may thwart amateurs, but not major governments.
9.5.2 Public-Key Cryptography
Secret-key systems are efficient because the amount of computation required
to encrypt or decrypt a message is manageable, but they have a big drawback: the
sender and receiver must both be in possession of the shared secret key. They may
even have to get together physically for one to give it to the other.
To get around
this problem,
public-key cryptography
is used (Diffie and Hellman, 1976).
This
Page 653
622
SECURITY
CHAP. 9
system has the property that distinct keys are used for encryption and decryption
and that given a well-chosen encryption key, it is virtually impossible to discover
the corresponding decryption key. Under these circumstances, the encryption key
can be made public and only the private decryption key kept secret.
Just to give a feel for public-key cryptography, consider the following two
questions:
Question 1: How much is 314159265358979
×
314159265358979?
Question 2: What is the square root of 3912571506419387090594828508241?
Most sixth graders, if given a pencil, paper, and the promise of a really big ice
cream sundae for the correct answer, could answer question 1 in an hour or two.
Most adults given a pencil, paper, and the promise of a lifetime 50% tax cut could
not solve question 2 at all without using a calculator, computer, or other external
help. Although squaring and square rooting are inverse operations, they differ enor-
mously in their computational complexity. This kind of asymmetry forms the basis
of public-key cryptography. Encryption makes use of the easy operation but de-
cryption without the key requires you to perform the hard operation.
A public-key system called
RSA
exploits the fact that multiplying really big
numbers is much easier for a computer to do than factoring really big numbers, es-
pecially when all arithmetic is done using modulo arithmetic and all the numbers
involved have hundreds of digits (Rivest et al., 1978).
This system is widely used
in the cryptographic world. Systems based on discrete logarithms are also used (El
Gamal, 1985).
The main problem with public-key cryptography is that it is a thou-
sand times slower than symmetric cryptography.
The way public-key cryptography works is that everyone picks a (public key,
private key) pair and publishes the public key. The public key is the encryption
key; the private key is the decryption key.
Usually, the key generation is auto-
mated, possibly with a user-selected password fed into the algorithm as a seed.
To
send a secret message to a user, a correspondent encrypts the message with the re-
ceiver’s public key. Since only the receiver has the private key, only the receiver
can decrypt the message.
9.5.3 One-Way Functions
In various situations that we will see later it is desirable to have some function,
f
, which has the property that given
f
and its parameter
x
, computing
y
=
f
(
x
) is
easy to do, but given only
f
(
x
), finding
x
is computationally infeasible. Such a
function typically mangles the bits in complex ways. It might start out by ini-
tializing
y
to
x
.
Then it could have a loop that iterates as many times as there are 1
bits in
x
, with each iteration permuting the bits of
y
in an iteration-dependent way,
adding in a different constant on each iteration, and generally mixing the bits up
very thoroughly. Such a function is called a
cryptographic hash function
.
Ace your assessments! Get Better Grades
Browse thousands of Study Materials & Solutions from your Favorite Schools
Concordia University
Concordia_University
School:
Operating_Systems
Course:
Great resource for chem class. Had all the past labs and assignments
Leland P.
Santa Clara University
Introducing Study Plan
Using AI Tools to Help you understand and remember your course concepts better and faster than any other resource.
Find the best videos to learn every concept in that course from Youtube and Tiktok without searching.
Save All Relavent Videos & Materials and access anytime and anywhere
Prepare Smart and Guarantee better grades
Know more
Students also viewed documents
lab 18.docx
lab_18.docx
Course
Course
3
Module5QuizSTA2023.d...
Module5QuizSTA2023.docx.docx
Course
Course
10
Week 7 Test Math302....
Week_7_Test_Math302.docx.docx
Course
Course
30
Chapter 1 Assigment ...
Chapter_1_Assigment_Questions.docx.docx
Course
Course
5
Week 4 tests.docx.do...
Week_4_tests.docx.docx
Course
Course
23
Week 6 tests.docx.do...
Week_6_tests.docx.docx
Course
Course
106
