


Modern Operating Systems by Herbert Bos and Andrew S. Tanenb...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdf
Showing 652653 out of 1137
Modern Operating Systems by Herbert Bos and Andrew...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdfM ODERN O PERATING S YSTEMS
Modern Operating Systems by Herbert...
Modern_Operating_Systems_by_Herbert_Bos_and_Andrew_S._Tanenbaum_4th_Ed.pdfM 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 915.
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 (letterforletter 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 twoletter 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
symmetrickey 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 256bit 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 PublicKey Cryptography
Secretkey 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,
publickey 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 wellchosen 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 publickey 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 publickey cryptography. Encryption makes use of the easy operation but de
cryption without the key requires you to perform the hard operation.
A publickey 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 publickey cryptography is that it is a thou
sand times slower than symmetric cryptography.
The way publickey 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 userselected 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 OneWay 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 iterationdependent 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:
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
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