RSA and RC4

Stream Cipher: RC4 and Block
Cipher: RSA
Implementation of RC4 Algorithm

 Implementation of RSA Algorithm
Symmetric key Cryptography
Symmetric Key Cryptography
 Basic ingredients of the scheme:
 Plaintext(P): Message to be encrypted.
 Secrete Key(K): Shared among the two parties.
 Ciphertext(C): Message after encryption.
 Encryption algorithm (EA): Uses P and K
 Decryption algorithm (DA): Uses C and K
 Security of the scheme

Depends on the secrecy of the key, Does not depend on the secrecy of the
algorithms.
 Assumptions:
Algorithms for encryption/decryption are known to the public, Keys used
are kept secret.
One-Time Pad
• Developed by Gilbert Vernam in 1918, another name: Vernam Cipher
• The key
– a truly random sequence of 0’s and 1’s
– the same length as the message
– use one time only
• The encryption
• adding the key to the message modulo 2, bit by bit.
Encryption c i  mi  ki i  1,2,3,...
m i  c i  ki i  1,2,3,...
Decryption
mi : plain-text bits.
ki : key (key-stream ) bits
ci : cipher-text bits.
Example
• Encryption:
• 1001001 1000110 plaintext
• 1010110 0110001 key
• 0011111 1110110 ciphertext
• Decryption:
• 0011111 1110110 ciphertext
• 1010110 0110001 key
• 1001001 1000110 plaintext
One-Time pad practical Problem
• Key-stream should be as long as plain-text

• Difficult in Key distribution & Management
• Solution :
– Stream Ciphers
– Key-stream is generated in pseudo-random fashion form Relatively
short secret key
Stream Cipher Structure
 Figure illustrates the general structure of a stream cipher, where a key is
input to a pseudorandom bit generator that produces an apparently random
key stream of bits, and which are XOR’d with message to encrypt it, and
XOR’d again to decrypt it by the receiver.
RC4
 RC4 is a stream cipher designed in 1987 by Ron Rivest for RSA Security. It
is a variable key-size stream cipher with byte-oriented operations.
Normally uses 64 bit and 128 bit key sizes.
 The algorithm is based on the use of a random permutation. Analysis shows

that the period of the cipher is likely to be greater than 10^100.
 Eight to sixteen machine operations are required per output byte, and the
cipher can be expected to run very quickly in software.
 RC4 is probably the most widely used stream cipher. SSL/TLS (Secure
socket, transport layer security) between web browsers and servers, IEEE
802.11 wirelss LAN std: WEP (Wired Equivalent Privacy), WPA (WiFi
Protected Access) protocol
 RC4 was kept as a trade secret by RSA Security, but in September 1994
was anonymously posted on the Internet
RC4 Key Schedule
RC4 Overview
Public-Key Cryptography
RSA Algorithm
 Invented in 1978 by Ron Rivest, Adi Shamir and Leonard Adleman
 Security relies on the difficulty of factoring large composite numbers
 The RSA scheme is a cipher in which the plaintext and ciphertext are
integers between 0 and n - 1 for some n. A typical size for n is 1024
bits. That is, n is less than 2^1024.
RSA Public Key Crypto System
Key generation:
1. Select 2 large prime numbers of about the same size, p and q
Typically each p, q has between 512 and 2048 bits
2. Compute n = pq, and (n) = (q-1)(p-1)
3. Select e, 1<e< (n), s.t. gcd(e, (n)) = 1
4. Compute d, 1< d< (n) s.t. ed  1 mod (n)

Knowing (n), d easy to compute.
Public key: (e, n)

Private key: (d, n)
RSA Description (cont.)
Encryption
Given a message M, 0 < M < n M  Zn
use public key (e, n)
compute C = Me mod n C  Zn
Decryption
Given a ciphertext C, use private key (d)
Compute Cd mod n = (Me mod n)d mod n = Med mod n = M
Cont.
C = Me mod (n = pq)
Plaintext: M Ciphertext: C
Cd mod n
From n, difficult to figure out p,q

From (n,e), difficult to figure d.
From (n,e) and C, difficult to figure out M s.t. C = Me
RSA Algorithm
RSA Example
 p = 11, q = 7, n = 77, (n) = 60
 d = 13, e = 37 (ed = 481; ed mod 60 = 1)
 Let M = 15. Then C  Me mod n

C  1537 (mod 77) = 71
 M  Cd mod n
M  7113 (mod 77) = 15
Thank You

RSA and RC4

Uploaded by

Copyright:

Available Formats

RSA and RC4

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

RSA and RC4

Uploaded by

Copyright:

Available Formats

Stream Cipher: RC4 and Block

Implementation of RC4 Algorithm

 Security of the scheme

• Key-stream should be as long as plain-text

 The algorithm is based on the use of a random permutation. Analysis shows

 Invented in 1978 by Ron Rivest, Adi Shamir and Leonard Adleman

 Security relies on the difficulty of factoring large composite numbers

2. Compute n = pq, and (n) = (q-1)(p-1)

3. Select e, 1<e< (n), s.t. gcd(e, (n)) = 1

4. Compute d, 1< d< (n) s.t. ed  1 mod (n)

Public key: (e, n)

From n, difficult to figure out p,q

 p = 11, q = 7, n = 77, (n) = 60

 d = 13, e = 37 (ed = 481; ed mod 60 = 1)

 Let M = 15. Then C  Me mod n

You might also like