Transcript Week - 13 to 16 - 6th Semester Notes

Case Study of Distributed
Operating System
(Week: 13)
 Case Study of Distributed Operating System
 Introduction
 A distributed operating system is the logical aggregation
of operating system software over a collection of
independent, networked, communicating, and physically
separate computational nodes. Individual nodes each hold a
specific software subset of the global aggregate operating
system. Each subset is a composite of two distinct service
provisioner. The first is a ubiquitous minimal kernel, or
microkernel, that directly controls that node’s hardware.
Second is a higher-level collection of system management
components that coordinate the node's individual and
collaborative activities. These components abstract
microkernel functions and support user applications
 Amoeba
 Introduction
 Originated at a university in Holland, 1981
 Currently used in various EU countries
 Built from the ground up. UNIX emulation added later
 Goal was to build a transparent distributed operating system
 Resources, regardless of their location, are managed by the
system, and the user is unaware of where processes are
actually run
 The Amoeba System Architecture
 Assumes that a large number of CPUs are available and that
each CPU ha 10s of Mb of memory
 CPUs are organized into processor pools
 CPUs do not need to be of the same architecture (can mix
SPARC, Motorola PowerPC, 680x0, Intel, Pentium, etc.)
 When a user types a command, system determines which
CPU(s) to execute it on. CPUs can be timeshared.
 Terminals are X-terminals or PCs running X emulators
 The processor pool doesn't have to be composed of CPU
boards enclosed in a cabinet, they can be on PCs, etc., in
different rooms, countries,...
 Some servers (e.g., file servers) run on dedicated processors,
because they need to be available all the time
The Amoeba System Architecture
 The Amoeba Microkernel
 The Amoeba microkernel is used on all terminals (with an
on-board processor), processors, and servers
 The microkernel manages processes and threads provides
low-level memory management support inter process
communication (point-to-point and group)handles low-level
I/O for the devices attached to the machine
 Process Management
 All processes are objects protected by capabilities
 Processes are managed at 3 levels
 by process servers, part of the microkernel
 by library procedures which act as interfaces
 by the run server, which decides where to run the processes
 Process management uses process descriptors
 Contains:
 platform description
 process' owner's capability
 etc
 Memory Management
 Designed with performance, simplicity and economics in
mind
 Process occupies contiguous segments in memory
 All of a process is constantly in memory
 Process is never swapped out or paged
 Communication
 Point-to-point (RPC) and Group
 Conclusion
 A distributed system potentially will be more reliable and
low cost than a time sharing system.
 By placing the other service outside the kernel and keeping
the kernel as small as possible, the system is more flexible
and reliable.
 The client-server model with remote procedure call have
proved that using basic primitive communication the
overhead of communication can be reduced.
 Amoeba is the only one Distributed Operating System
which implements Wide Area Network.
Managing Multiple processing
System
(Week:14)
Multi-processor scheduling
 If Multiple CPUs are available, load sharing becomes
possible, but the scheduling problem becomes
correspondingly more complex.
 Many possibilities have been tried, but there is no optimal
solution is available.
 If the processors are identical—homogeneous—in terms
of their functionality; we can then use any available
processor to run any process in the queue.
 Loosely coupled multiprocessor or cluster
 Consists of a collection of relatively autonomous system,
each processor has its own memory and I/O channels.
Multi-processor scheduling…
 Tightly coupled multiprocessing
 Consists of a set of processors that share a common main
memory and are under the integrated control of an operating
system
 The discussion on the following slides is based on the
tightly coupled multiprocessing.
 When a computer system contains more than a single
processor, several new issues are introduced into the design
of scheduling function.
 Design Issues
 The assignment of processes to processors
 The use of multiprogramming on individual processors
 The actual dispatching of a process
 Multiple processor Scheduling…
 Assignment of Processes to Processors
 Symmetric multiprocessing – All processors are
autonomous (act independently) and treated equally.
 There is one copy of the supervisor or kernel that can
only be executed by all processors concurrently.
 However, concurrent access to the shared data structure
need to be controlled i.e. only one processor to execute
the operating system at a time.
 This method is called floating master.
 The symmetric configuration is the most flexible and
versatile of all the configurations.
 Master/Slave assignment
Kernel functions always run on a particular processor.
Other processors execute user processes.
 Advantage: Resource conflict resolution simplified since
single processor has control.
 Problem: Failure of master processor? Master processor
does the scheduling ==> bottleneck.
 Peer assignment
 OS can execute on any processor. Each processor does its
own scheduling from the pool of available processes. This is
similar to Solaris or NT symmetric multiprocessing (SMP).

 The use of multiprogramming on individual processors
 We are concerned to provide the best performance, on
average for the applications.
 An application that consist of a number of threads may run
poorly unless all of its threads are available to run
concurrently.
 Process Dispatching
 Actual selection of process to run.
 Single processor multiprogramming strategies may be
counter-productive here.
 Simpler approach may be more effective with less overhead.
 Thread scheduling: An application can be implemented as
a set of threads that cooperate and execute concurrently in
the same address space. Criteria: When related threads run
in parallel performance improves.
 Load sharing or Self scheduling : Processes are not
assigned to a particular processor. A global queue of ready
threads is maintained and each processor when idle
selects a thread from queue . Disadvantage, centre queue
must be accessed in a manner to enforce mutual
exclusion, because many processors look for the work at
the same time. However, it is most commonly used
schemes.
 Gang scheduling: A set of related threads is scheduled to
run on a set of processors at the same time on a one-toone basis. Scheduling overhead, but good performance.
Multi-processor scheduling…
 Thread Scheduling…


Dedicated processor assignment: It is the extreme form
of gang scheduling. Each program is allocated a number
of processors equal to the number of threads in the
program, for the duration of the program execution.
Dynamic scheduling: More like demand scheduling.
Real-Time Operating System
(Week:15)
 INTRODUCTION
 Real Time Operating system (RTOS) is specially designed to





run applications with very precise timing and a high degree
of reliability.
This can be especially important in measurement and
automation systems where downtime is costly or a program
delay could cause a safety hazard.
RTOS has an advanced algorithm for scheduling (response fast).
Scheduler flexibility enables a wider, computer-system
orchestration (arrangement) of process priorities, but a real-time
OS is more frequently dedicated to a narrow set of applications.
Key factors in a real-time OS are minimal interrupt latency and
minimal thread switching latency;
a real-time OS is valued more for how quickly or how predictably
it can respond than for the amount of work it can perform in a
given period of time.
 NECESSITY OF RTOS
 A key characteristic of an RTOS is the level of its consistency




concerning the amount of time it takes to accept and complete an
application's task;
Hard real time OS must have known maximum time for each of
the critical operations that it performs . Examples are airbag
system for a new car, missile firing etc... A hard real-time
operating system has less jitter.,
Soft real time OS only guarantee a maximum most of the
time. Soft real-time operating system has more jitter (e.g. mobile
phone received shaky video).
The chief design goal is not high throughput, but rather a
guarantee of a soft or hard performance category.
An RTOS that can usually or generally meet a deadline is a soft
real-time OS, but if it can meet a deadline deterministically it is a
hard real-time OS.
 Systems Classification
 Non Real Time systems
 A non real time system is a system where there are no
deadlines involved. Non-RT systems could be described as
follow:
 ”A non real time system is a system where the programmed
reaction to a stimulus will certainly happen sometime in the
future”.
 Soft Real Time (SRT) systems
 A Soft real time system is a system where not meeting a
deadline can have undesirable but not catastrophic effects, a
performance degradation for example SRTs could be
described as follow:
 ”A soft real time system is a system where the programmed
reaction to a stimulus is almost always completed within a
known finite time”.
 Systems Classification…
 Hard Real Time systems
 An Hard Real Time (HRT) system is a system where not
meeting a deadline can have catastrophic effects. HRT
systems require a much more strict definition and could be
described as follow:
 ”An hard real time system is a system where the
programmed reaction to a stimulus is guaranteed to be
completed within a known finite time”.
Embedded systems
 An embedded system is a computer system designed for
specific control functions within a larger system, often
with real-time computing constraints.
 It is embedded as part of a complete device often including
hardware and mechanical parts (for e.g. heavy duty printer
and Intelligent workstation connected with a mini or
mainframe computer)
 By contrast, a general-purpose computer, such as a personal
computer, is designed to be flexible and to meet a wide
range of end-user needs.
 Embedded systems control many devices in common use
today.
Embedded systems…
 Embedded systems contain processing cores that are
either microcontroller or digital signal processor.
 The key characteristic, however, is being dedicated to
handle a particular task.
 Since the embedded system is dedicated to specific tasks,
design engineers can optimize it to reduce the size and cost
of the product and increase the reliability and
performance.
 Some embedded systems are mass-produced, benefiting
from economies scale.
Embedded systems…
 Physically, embedded systems range from portable
devices such as digital watches and MP3, to large
stationary installations like traffic lights, factory
controllers (PLC’s: programmable logic controller).
 Complexity varies from low, with a
single microcontroller chip, to very high with multiple
units, peripherals and networks mounted inside a
large chassis or enclosure.
 Generally Embedded systems consists of
Microcontroller , RAM and ROM (contains RTOS)
Examples & Applications
 Telecom
 Missiles and Satellites,
 Computer Networking,
 Digital Consumer Electronics, and
 Automotive
 Mobile phone
 Digital camera
 Robots
 Point of sales terminals
Examples & Applications…
 Automatic Chocolate Vending Machine
 Stepper motor controllers for a robotics system
 Washing or cooking system
 Multitasking Toys
 Microcontroller- based single or multi-display
 digital panel meter for voltage, current, resistance
 and frequency
 Keyboard controller
Operating System Security
(Week:16)
Resource Security & Protection
 Introduction
 Deals with the control of unauthorized use of software and
hardware.
 Business applications such as banking requires high security
and protection during any transaction
 Security techniques should not only prevent the misuse of
secret information but also its destruction
 Basic Terminology
 Potential Security Violations

Unauthorized information release : unauthorized person
is able to read information, unauthorized use of computer
program

Unauthorized information modification: unauthorized
person is able to modify information e.g. changing grade
of a university student, changing account balances in
bank databases

Unauthorized denial of service : Unauthorized person
should not succeed in Preventing an authorized person
from accessing the information
External vs. Internal Security
 External Security

Also called physical security

Deals with regulating the access to premises of

computer systems [ e.g. hardware, disks, tapes]

Can be enforced by placing a guard at the door, by

giving a secret key to authorized person.

Issues to be dealt are administrative
 Internal Security

Deals with the use of computer hardware and software

information stored in computer systems

Requires an issue of authentication
Policies and Mechanisms
 Policy
•
What should be done?
•
Policy gives assignment of the access rights to users to
•
various resources.
•
Policies Decides which user has access to what resources
•
Policies can change with Time and application
 Mechanism

How it should be done?

Protection mechanism provides a set of tools that can be

used to design or specify a wide array of protection

policies

Protection mechanism in OS controls user access to system

resources.

Protection Scheme must be amenable to a wide variety of

policies.

Protection is a mechanism and Security is a policy.
 Protection Domain of a Process
 Specifies Resources that a process can access and type of
operation that a process can perform on the resources.
 Required for enforcing security
 Allow the process to use only those resources that it
requires.
 Every process executes in its protection domain and
protection domain is switched appropriately whenever
control jumps from process to process.
 Advantage :
“Eliminates the possibility of a process breaching security
maliciously or unintentionally and increases accountability”
Design Principles for a Secure System
 Economy
 Protection mechanism should be economical to develop and use.




Should add extra high costs for the system?.
Complete Mediation
 Requires that every request to access an object be checked for the
authority to do so.
Open Design
 A protection mechanism should work even if its underlying
principles are known to the attacker.
Separation of Privileges
 Protection Mechanism requires two keys to unlock a lock i.e.
should satisfy two independent conditions before an access is
allowed.
Least Privilege
 Subject should be given bare minimum access rights that are
sufficient for completion of task.
 Least Common Mechanism
 Portion common to more than one user should be
minimized. Coupling among users represents potential
information path between users and hence a potential threat
to their security.
 Acceptability
 Protection Mechanism must be simple to use.
 Fail-Safe Defaults
 Default case should mean lack of access (due to any reason
few ways to access). If a design or implementation mistake
is responsible for denial of an access, it will eventually be
discovered and be fixed.
 Access Matrix Model

Model proposed by Lampson. Enhanced and Refined further
by Graham, Denning and Harrison.

Protection System consists of mechanism to control user
access for various resources or to control information flow.

Current Objects

Finite set (‘O’) of entities to which access is to be
controlled. [Files]

Current Subjects

Finite set (‘S’) of entities that access current objects. e.g.
subject may be a process. Subjects themselves can be
treated as objects and can be accessed like an object by
other subjects. [Users]

Generic Rights

A finite set of generic rights R={r1,r2,r3,……rm} gives
various access rights that subjects can have to objects e.g.
read, write , execute .own , delete etc
 Protection State of a System :
 Protection state of a system is represented by a triplet (S,O,P)
 Access Matrix has a row for every current subject and a
column for every current object.
(S,O,P)
Access Matrix
Set of current objects
Set of current subjects
Access Matrix Model cont..
Objects
o
s
Subjects
P[s,o]
P[s,o] is a subset of R, the generic rights and denotes the access
rights which subject S has to object O.
Access Matrix Representing Protection State
O1
O2
O3
O4
O5
S1
read,
write
own,
delete
own
sendmail
recmail
S2
execute
copy
recmail
own
block,
wakeup
S3
own
read,
write
sendmail
block,
wakeup
own


Access matrix Model cont…
Enforcing a Security Policy
1.
A security Policy is enforced by validating every user
access for appropriate access rights
2.
Every Object has a monitor that validates all accesses to
that object in the following manner:
(i) A subject ‘s’ requests an access ‘α’ to object ‘o’.
(ii) Protection System presents triplet(s,α,o) to monitor of ‘o’
(iii) Monitor looks into access rights of ‘s’ to ‘o’. If α belongs
to subset of P[s,o] then access is permitted Else it is
denied.

Implementation of Access Matrix Model

Three Implementations of Access matrix model

Capabilities Based

Access Control List

Lock-key Method
 Capabilities
 Capability based method corresponds to the row-wise
decomposition of the access matrix.
 Each subject s is assigned a list of tuples (o, P [s , o]) for all
objects o that it is allowed to access. These tuples are known
as capability.
 Typical view of capability
Object
Descriptor
Access Rights
read , write, execute etc.
•Capability has two fields. Object Descriptor (address of the
corresponding object for e.g. address of a word within an
object) is identifier for objects and the second allowed
access rights (read, write etc. )for the object.
 Capabilities cont..
 Possession of a capability treated as a evidence that user has
authority to access the object in the ways specified in the
capability.
 At any point of time, a subject is authorized to access only
those objects for which it has capabilities.

Capability Based Addressing




Capabilities can be used for addressing mechanism by the
system using object descriptor
The Main advantage of using capability as an addressing
mechanism that it
provides an address that is context independent absolute
address
However, System must allow embedding of capabilities
in user programs and data structures.
Capability Based Addressing cont..
An address in a program
Capability id
length
Offset
base
Object Table
offset
Object
Descriptor
Access
Rights
Capability list of the user
length
 Capability Based Addressing cont..
 A user Program issues a request to access a word with an





object.
Address contains capability ID of the object and an offset
with in the object
System uses capability ID to search the capability list of the
user to locate the capability that contains the allowed access
rights and an object descriptor.
System checks the access rights.
Object descriptor is used to search the object table to locate
entry for the object.
Object entry contains the base address of the object in main
memory.

Capability Based Addressing cont..

Two Salient features :
Re-locatability [ An object can be relocated any where
within main memory without changing the capability]
Sharing[ Several programs can share the same object with
different names for the same object]
Implementation Considerations:
To maintain a forgery-free capability, a user should not be
able to access [read, modify or construct] a capability.
Two ways for implementation:
Tagged approach
Partitioned approach


















Capability Based Addressing cont..
Tagged approach :
One or more bits are attached to each memory location and
every processor tag indicates whether a memory word or
register contains a capability.
If tag = ON , the information is capability otherwise ordinary
data.
When tag =ON user can not manipulate the word.
Example: Burroughs B6700
Partitioned Approach:
Capabilities and Ordinary data are partitioned[ stored
separately]
Every object has two segments : one for data other for
capabilities
Processor has two sets of registers : one for data other for
capabilities
Examples : Chicago Magic Number Machine, Plessey System
Advantages Drawbacks of Capabilities

Advantages

Efficient : validity can be easily tested

Simple : due to natural correspondence between
structural properties of

capabilities and semantic properties of addressing
variables.

Flexible : user can decide which of his address contain
capabilities
Disadvantages:

Control of propagation

Review

Revocation of access rights

Garbage Collection
Access Control List Method








Column wise decomposition of the access matrix.
Each object ‘o’ is assigned a pairs (s, P[s,o]) for all subjects
s that are allowed to access the object.
P[s,o] denotes the access rights that subject s has to ‘o’
When a subject ‘s’ requests access ‘α’ to object ‘o’, it is
executed in the following manner:
System searches the access control list of ‘o’ to find out if
an entry(s,Ø) exists
for subject ‘s’.
If exists then system checks for whether access is
permitted (α belongs to Ø)
If yes access is granted otherwise a Exception is raised.
Schematic of an access control list
Subjects
Access Rights
Smith
read,write,execute
Jones
read
Lee
write
Grant
execute
Execution efficiency of the access control list method is poor because an
access control list must be searched for every access to a protected
object.

Access Control List Method cont..

Main features :
Easy Revocation: Revocation of access rights is simple,
fast and efficient. Can be
achieved simply by removing subject’s entry from
object’s access control list.
Easy review of an access: Can be easily determined what
subjects have access rights to
an object
Implementation Considerations
Efficiency of Execution : Since access control list needs
to be searched for every access to a protected object, it
can be very slow. [Can be avoided using shadow
registers]
Efficiency of storage: List may require a huge amount of
storage [ Can be avoided using protection groups]








Lock Key Method




1.
2.
Hybrid of the capability-based method and access control list
method
Every subject has a capability list that contains tuples of the
form (O,k) indicating that the subject can access Object O
using key k.
Every Object has an access control list that contains tuples of
the form (l,y) called a lock entry. It indicates that any subject
which can lock l can access this object in modes contained in
y.
When a subject makes a request to access object o in α , the
system is executed in the following manner:
System locates tuple (o,k) in the capability list of the subject.
If no such tuple is found access is not permitted
Otherwise access is permitted only if there exists a lock entry
(l,y) in the access control list of the object o such that k=l and
α belongs to y.
 Data Security
 Unauthorized User can gain access to confidential
information
 User may by pass protection mechanism of system
 To add extra protection techniques are needed to ensure the
an intruder is unable to understand or make use of any
information obtained by wrongful access.
 Cryptography can be used for extra protection
 Converting one piece text in to cryptic form before storing it
on to computer
 Model of Cryptography
 Plaintext (or a cleartext) is the original message that is to be
converted into encrypted form
 Ciphertext: is a message in encrypted form
 Encryption: is process of converting a plaintext to ciphered
text
 Decryption: is the process of converting ciphertext back to
plaintext text
 Cryptosystem: is the system for encryption and decryption
of information
 Symmetric Cryptography : If the key is same for both
encryption and decryption
 Asymmetric Cryptography : If the key is not same for both
encryption and decryption
General Structure of a Cryptographic System
SI
M
CA
m
M
E
D
C = Eke(M)
Ke
Kd
Encrption key
Decrption key
M = Plain text , Ke= Encryption key, C = Ciphertext =
EKe(M), EKe = Encryption operation using Ke
CA=CryptoAnalyst (Intruder), SI=Side Information
(freq. of letters & words), Kd=Decryption Key

Design Principles





Shannon’s principle :
Principle of Diffusion : Spreading the correlation and
dependencies among key- string variables over substrings
To maximize the length of the plaintext needed to break the
system
Principle of confusion : change the piece of information so that
output has no oblivious relation with the input.
Exhaustive search principle:

Determination of key needed to break the system
Requires exhaustive search of a space.
Classification of Cryptographic Systems
Cryptographic Systems
Conventional
Modern
Systems
Systems
Open design
Private key
Systems
Public key
Systems

Conventional Cryptography

Caesar Cipher
A letter is transformed into third letter following in the
alphabetical sequence
E : M(M+3)modulo 26, where 0<=M<=25
For e.g. “APOS” transformed to “DSRV”
Disadvantage : Simple search
Simple substitution
Any permutation (grouping or combination of a set of things)
of letters can be mapped to English Letters for e.g. 3! (6
possible combination of any message can be made). Positional
correlation is eliminated. Since each permutation of letters is a
key, there are 26!(>10^26) keys to search i.e. very exhaustive
or expensive
3. Polyalphabetic Ciphers:








It uses a number of substitutions at different positions in the
message (for e.g. A or B may be replaced or substituted by any
letter of the 26 alphabet), where a unit from the plaintext is mapped
to one of several possibilities in the Ciphertext and vice versa.

System switches among n substitution alphabet ciphers
periodically.

Modern Cryptography


Private key Cryptography : Data Encryption Standard
(DES) developed by IBM
Two basic operations :

Permutation : permutes the bits of a word to provide
diffusion

Substitution : replaces m-bit input by an n-bit output.
No simple correlation between input and output. The
purpose of it to provide confusion.

Data Encryption Standard [DES]







DES is a block cipher that crypts (secret) 64-bit data blocks
using 56-bit key
Error detection is provided by adding 8-bit parity
Three steps:
Plain text undergoes initial permutation(IP) in which 64 bits of
the block is permuted
Permuted block goes a complex transformation using a key and
involves 16 iterations
The output of step(2) goes a final permutation which is the
inverse of step(1)
The output of step(3) is ciphered text block
Data Encryption Standard [DES]Iterative Transformation
Li-1
Ri-1
•Iterative Transformation step consists
of 16 functionally identical iterations
•Let Li and Ri respectively denote the
left and right 32 bit halves of the
crypted 64-bit block after the ith.
Iteration (1<=i<=16).
f
θ
Li
Ri=Li θ f(Ri-1,Ki)
Li
•
•
•
•
•
Ki
Key
Ri
Steps:
32-bit Ri-1 is expanded to 48-bit E(Ri-1)
Ex-OR operation is performed between 48-bit key Ki and E(Ri-1). 48 bit output is
partitioned into 8 partitions Q1,Q2,….Q8 of 6bits each
Each Qi, 1<=i<=8 is fed into a separate 6-to-4 substitution box (A 6 to 4 substitution
box transforms 6 bits into 4 bits for secrecy .
32-bit output of 8 substitution boxes is fed to a permutation box whose 32 bit output is
f
Decryption of DES
 The decryption of crypted block requires the
execution of the three previously described steps in
reverse order.
 With the reverse function performed at each step

Public Key Cryptography








Encryption Procedure E is in public domain
Decryption Procedure D is kept secret
Encryption procedure E and Decryption procedure D
must satisfy following properties:
For every message M, D(E(M)) = M
E and D can be efficiently applied to any message M
Knowledge of E does not compromise security.
i.e. It should be impossible to derive D from E
Public key cryptography allows two users to have
secure communication even if they have not
communicated before
 Rivest-Shamir-Adleman Method (RSA)
 Popularly known as RSA method
 Binary Plaintext is divided into blocks. Each block is






represented by an integer between 0 and n-1
Encryption key is a pair (e , n) where e is positive integer
Message M (between 0 and n-1) is encrypted by raising it to
eth power modulo n i.e. the ciphertext C corresponding to a
message M is given by
C = M^e modulo n
Cipher text C is an integer between 0 and n-1.
Encryption does not increase the length of plaintext
Decryption key is a pair (d,n) where d is a positive integer.
Cont..
 Rivest-Shamir-Adleman cont..
 Cipher text block C is decrypted by raising it to dth power
modulo n i.e. plain text M corresponding to a ciphertext C is
given by
 M = C^d modulo n
 A User X possesses an encryption key(eX,nX) and a
decryption key(dX,nX) where the encryption key is
available in public domain, but the decryption key is known
only to user X.
 Whenever a user Y wants to send a message M to user X, Y
simply uses X’s encryption key (eX,nX) to encrypt the
message. When X receives the encrypted message, it
decrypt it using its decryption key (dY,nX).
 A schematic of the RSA is shown on next slide.
Rivest-Shamir-Adleman cont..
M
e
M mod n
(e , n)
Encryption Key for user
e
C = M mod n
d
C mod n
(d , n)
Decryption Key for user
M

Rivest-Shamir-Adleman Method

Determination of Keys
Chose two large prime numbers p and q and define n as
n=p*q
p and q should be chosen such that it will be practically
impossible to determine p and q by factoring n.
Chose any large integer d, which is relatively prime (two
integers are relatively prime if they share no common
positive factors divisors except 1) to the following
equation:GCD(d,(p-1) * (q-1)) =1
(GCD is greatest common divisor)
Integer e is computed from p , q and d as follows:
e * d (modulo (p-1) * (q-1)) = 1








Greatest Common Divisor (GCD) using the Euclidean Algorithm
 This page will use the Euclidean Algorithm to find the GCD
of two given numbers and show you the steps taken to get
it.
 The Euclidean Algorithm uses the principle that
subtracting one of the numbers from the other does not
change the GCD.
 This the same thing as repeatedly setting the larger number
to the remainder of the larger number divided by the
smaller number.
 If the GCD is 1, the two numbers are said to be co-prime or
relative prime to each other.
Greatest Common Divisor (gcd) using
the Euclidean Algorithm
a
b
Next step
40
23
40>=23; therefore a = 40 mod 23
17
23
23 > 17;therefore b = 23 mod 17
17
6
17>= ; therefore a = 17 mod 6
5
6
6 > 5; therefore b = 6 mod 5
5
1
B ==1; thus the gcd is 1
Encryption and Decryption Key example
 Initialization
 M=8 (message
 Let p=5, q=11, n =p x q =55 and (p-1) x (q-1)=40
 Choose d=23, because 23 and 40 are relatively prime to
(GCD(23,40)=1).
 Now choose e to satisfy the following condition: 23 x e (mod 40) =1
 e = 7 satisfies the above condition
 Encryption
 C = M^e mod n ; 8^7 mod 55 = 2
 Decryption
 M = C^d mod n ; 2^23 mod 55 = 8