程序代写代做代考 chain Excel algorithm Reliable Data Transfer Protocol

Reliable Data Transfer Protocol

RSA with Cipher Block Chaining (RSA-CBC)
Assignment #3

RSA: Choosing keys
1. Choose two large prime numbers p, q.
(e.g., 1024 bits each)
2. Compute n = pq, z = (p -1)(q -1)
3. Choose e (with e < n) that has no common factors with z. (e, z are 'relatively prime'). 4. Choose d such that ed -1 is exactly divisible by z. (in other words: ed mod z = 1 ). 5. Public key is (n, e). Private key is (n, d). In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. The first 30 prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, and 113 Magic happens! RSA: Encryption, decryption 0. Given (n,e) and (n,d) as computed above 1. To encrypt bit pattern, m, compute c = m mod n e (i.e., remainder when m is divided by n) e 2. To decrypt received bit pattern, c, compute m = c mod n d (i.e., remainder when c is divided by n) d m = (m mod n) e mod n d RSA example: Bob chooses p=5, q=7. Then n=35, z=24. e=5 (so e, z relatively prime). d=29 (so ed-1 exactly divisible by z) (equivalently, ed mod z = 1). letter m m e c = m mod n e l 12 248832 17 c m = c mod n d 17 481968572106750915091411825223072000 - too big !! (int type) 12 c d letter l encrypt: decrypt: c d = How to solve this problem: Repeated Squaring: calculate y = x e mod n int repeatSquare( int x, int e, int n) { y=1;//initialize y to 1, very important while (e > 0) {
if (( e % 2 ) == 0) {
x = (x*x) % n;
e = e/2;
}
else {
y = (x*y) % n;
e = e-1;
}
}
return y; //the result is stored in y
}

Use repeatSquare either for encryption or decryption
c = me mod n
m = cd mod n

Hint:
Solve for n.
Solve for z.
Choose d, such that the following condition holds:
(ed-1) mod z = 0
Exercise: Find the private key

Given: p=13, q=17 and e= 5

Find d.

There is more than one possible answer.
Excel worksheet: RSA_Exercise_find_d.xlsx

Summary of Techniques
Check if e & z are coprimes.
Euclidean Algorithm gcd(e,z):
zx + ed = gcd(z,e)=1
Solve for d
Extended Euclidean Algorithm
Bézout’s identity.

Real example of RSA keys

n=
A9E167983F39D55FF2A093415EA6798985C8355D9A915BFB1D01DA197026170F
BDA522D035856D7A986614415CCFB7B7083B09C991B81969376DF9651E7BD9A9
3324A37F3BBBAF460186363432CB07035952FC858B3104B8CC18081448E64F1C
FB5D60C4E05C1F53D37F53D86901F105F87A70D1BE83C65F38CF1C2CAA6AA7EB

e=010001

d=
67CD484C9A0D8F98C21B65FF22839C6DF0A6061DBCEDA7038894F21C6B0F8B35
DE0E827830CBE7BA6A56AD77C6EB517970790AA0F4FE45E0A9B2F419DA8798D6
308474E4FC596CC1C677DCA991D07C30A0A2C5085E217143FC0D073DF0FA6D14
9E4E63F01758791C4B981C3D3DB01BDFFA253BA3C02C9805F61009D887DB0319

This is the real thing!
http://www.di-mgt.com.au/rsa_alg.html#realexample
1024-bit RSA encryption key (in hex format):

Sample Small Keys
N=77

e = 7;
d = 43;

e = 13;
d = 37;

e = 17;
d = 53;

e = 19;
d = 79;
e=3;
d=16971;
n=25777;
Use bigger keys like this!

Real example of RSA

P = 96130345313583504574191581280615427909309845594996215822583150879647940

e = 35535
d = 58008302860037763936093661289677917594669062089650962180422866111380593852

Data Communications and Networking by B. Forouzan

Cryptography
Cipher Block Chaining
RSA with
Avoid generating the same ciphertext for identical plaintext blocks
Avoid sending twice the number of ciphertext bits by applying a formula to calculate the sequence of random numbers automatically, except for the very first random number.

RSA with Cipher Block Chaining
Avoid sending twice the number of ciphertext bits
RSA-Cipher Block Chaining (RSA-CBC): the message is encrypted in blocks of k bits XOR random number.
m(i) = ith plaintext block
c(i) = ith ciphertext block
a b = XOR of two bit strings
Ke= block-cipher encryption algorithm with key e
= random number to be used by 1st ciphertext block
c(0) = IV (Initialisation Vector) = random k-bit string
To encrypt: XOR,
To decrypt: , XOR
involves the public key
involves the private key
This is a number that is used only once (nonce)

RSA with Cipher Block Chaining
Avoid sending twice the number of ciphertext bits
RSA-Cipher Block Chaining (RSA-CBC): the message is encrypted in blocks of k bits XOR random number.
m(i) = ith plaintext block
c(i) = ith ciphertext block
a b = XOR of two bit strings
Ke= block-cipher encryption algorithm with key e
c(0) = IV = random number to be used by 1st ciphertext block
Step 1. Generate a random k-bit number, store as IV and c(0).
Example:

k=3
plaintext = 010 010 010

m(1)

m(2)

m(3)
r(1)=c(0)= IV
r(2)=c(1)
r(3)=c(2)

c(0) = IV (Initialisation Vector) = random k-bit string
c(1) = Ks (m(1) c(0) )
Step 2. Calculate the ciphertext for block 1.
To encrypt: XOR,

RSA with Cipher Block Chaining
Avoid sending twice the number of ciphertext bits
c(0) = IV = random number to be used by 1st ciphertext block
Step 1. Generate a random k-bit number, and store as the Initialisation Vector (IV) and c(0).
Example:

k=3
plaintext = 010 010 010

m(1)

m(2)

m(3)
r(2)=c(1)
r(3)=c(2)

c(1) = Ke (m(1) c(0) )
Step 2. Calculate the ciphertext for block 1.
c(i) = Ke (m(i) c(i-1) )
Step 3. Calculate the remaining ciphertext for block i.
r(1)=c(0)= IV
To encrypt: XOR,
RSA-Cipher Block Chaining (RSA-CBC): the message is encrypted in blocks of k bits XOR random number.

k=3
plaintext = 010 010 010

m(1)

m(2)

m(3)
r(2)=c(1)
r(3)=c(2)

c(1) = Ke (m(1) c(0) )
Step 2. Calculate the ciphertext for block 1.
c(i) = Ke (m(i) c(i-1) )
Step 3. Calculate the remaining ciphertext for block i.
r(1)=c(0)= IV
Example: To encrypt: XOR,
RSA-Cipher Block Chaining (RSA-CBC): the message is encrypted in blocks of k bits XOR random number.

k=3
plaintext = 010 010 010

m(1)

m(2)

m(3)
r(2)=c(1)
r(3)=c(2)

c(1) = Ke (m(1) c(0) )
Step 2. Calculate the ciphertext for block 1.
c(i) = Ke (m(i) c(i-1) )
Step 3. Calculate the remaining ciphertext for block i.
c(0) = IV = 001

r(1)=c(0)= IV
Example: To encrypt: XOR,
RSA-Cipher Block Chaining (RSA-CBC): the message is encrypted in blocks of k bits XOR random number.

k=3
plaintext = 010 010 010

m(1)

m(2)

m(3)
r(2)=c(1)
r(3)=c(2)

c(1) = Ks (m(1) c(0) )
Step 2. Calculate the ciphertext for block 1.
c(i) = Ke (m(i) c(i-1) )
Step 3. Calculate the remaining ciphertext for block i.
c(0) = IV = 001

c(1) = Ke (m(1) c(0) ) = Ke (010 001 ) =100
r(1)=c(0)= IV
Example: To encrypt: XOR,
RSA-Cipher Block Chaining (RSA-CBC): the message is encrypted in blocks of k bits XOR random number.

k=3
plaintext = 010 010 010

m(1)

m(2)

m(3)
r(2)=c(1)
r(3)=c(2)

c(1) = Ks (m(1) c(0) )
Step 2. Calculate the ciphertext for block 1.
c(i) = Ks (m(i) c(i-1) )
Step 3. Calculate the remaining ciphertext for block i.
c(0) = IV = 001

c(1) = Ke (m(1) c(0) ) = Ke (010 001 ) =100
c(2) = Ke (010 100 ) = 000
r(1)=c(0)= IV
Example: To encrypt: XOR,
RSA-Cipher Block Chaining (RSA-CBC): the message is encrypted in blocks of k bits XOR random number.

RSA with Cipher Block Chaining
Avoid sending twice the number of ciphertext bits
Step 1. Generate a random k-bit number, and store as the Initialisation Vector (IV) and c(0).
Example:

k=3
plaintext = 010 010 010

m(1)

m(2)

m(3)
r(1)=c(0)=IV
r(2)=c(1)
r(3)=c(2)

Step 2. Calculate the ciphertext for block 1.
Step 3. Calculate the remaining ciphertext for block i.
c(0) = IV = 001
c(1) = Ke (m(1) c(0) ) = Ke (010 001 ) =100
c(2) = Ke (010 100 ) = 000
c(3) = Ke (010 000 ) = 101
Example: To encrypt: XOR,
RSA-Cipher Block Chaining (RSA-CBC): the message is encrypted in blocks of k bits XOR random number.

RSA with Cipher Block Chaining
Avoid sending twice the number of ciphertext bits
Step 1. Generate a random k-bit number, and store as the Initialisation Vector (IV) and c(0).
Example:

k=3
plaintext = 010 010 010

m(1)

m(2)

m(3)
r(1)=c(0)=IV
r(2)=c(1)
r(3)=c(2)

Step 2. Calculate the ciphertext for block 1.
Step 3. Calculate the remaining ciphertext for block i.
c(0) = IV = 001
c(1) = Ke (m(1) c(0) ) = Ke (010 001 ) =100
c(2) = Ke (010 100 ) = 000
c(3) = Ke (010 000 ) = 101
Step 4. Send c(0),c(1),c(2),c(3)=001,100,000,101
Example: To encrypt: XOR,
RSA-Cipher Block Chaining (RSA-CBC): the message is encrypted in blocks of k bits XOR random number.

RSA with Cipher Block Chaining
Avoid sending twice the number of ciphertext bits
Example:

k=3
plaintext = 010 010 010

m(1)

m(2)

m(3)
r(1)=c(0)=IV
r(2)=c(1)
r(3)=c(2)

Step 1. Given c(0),c(1),c(2),c(3),…
For each ciphertext block, calculate Ks (c(i)), starting at i=1

c(0)
Given c(0),c(1),c(2),c(3)=001,100,000,101
Kd (c(1))= Ks (100)=011

c(1)
Kd (c(2))= Kd (000)=110
Kd (c(3))= Kd (101)=010
Example: To decrypt: , XOR

RSA-Cipher Block Chaining (RSA-CBC): the message is encrypted in blocks of k bits XOR random number.

RSA with Cipher Block Chaining
Avoid sending twice the number of ciphertext bits
Example:

k=3
plaintext = 010 010 010

m(1)

m(2)

m(3)
r(1)=c(0)=IV
r(2)=c(1)
r(3)=c(2)

Step 1. Given c(0),c(1),c(2),c(3),…
For each ciphertext block, calculate Kd (c(i)), starting at i=1
Given c(0),c(1),c(2),c(3)=001,100,000,101
Kd (c(1))= Ks (100)=011
Kd (c(2))=110
Kd (c(3))=010
Step 2. For each ciphertext block, calculate m(i)= Kd(c(i)) r(i)
m(1)= Kd(c(1)) r(1) = 011 001=010
m(2)= Kd(c(2)) r(2) = 110 100=010
m(3)= Kd(c(3)) r(3) = 010 000=010

Example: To decrypt: , XOR

RSA-Cipher Block Chaining (RSA-CBC): the message is encrypted in blocks of k bits XOR random number.

RSA with Cipher Block Chaining
IMPLEMENTATION TIPS

General Sequence of Events

RSA with CBC
CLIENT
SERVER
Port
1024
time
time
Passive open
Active open
TCP connection to Port 1024 established
Port
1120
Determine which key set to use from predefined 3 key sets
Send public key: e, and n
get user input (message)
Receive e(nonce)
Extracts nonce: d(e(nonce))
Receive public key: e, and n
Generate nonce
send OK
Send e(nonce).
Use public key to encrypt nonce: e(nonce)
Receive encrypted message
Decrypt message using RSA with CBC (d, n, nonce)
display original message
display decrypted message
echo back the decrypted message
Use RSA with CBC (e, n, nonce) to encrypt message:
Send encrypted message
display received message
(e, n)
e(nonce)
OK
Cipher text
decrypted text
This is a number that is used only once (nonce)
Note: any ephemeral port would suffice

RSA_CBA Encryption
Encryption is performed on the index number of the character XORed with a random number.
CLIENT
‘\n’
send_buffer
0
1
2
3
A
A
A
c = m mod n
e
ENCRYPTION:

65
65
65
index

1171
22390
1953
Similar to CBC
User entry
10

nonce: 1234
9603
m XOR calcRandNum
encrypted
number
cipher =
encrypt(m XOR calcRandNum)
22327
2016
9609
9021

RSA_CBA Decryption
Decryption is performed on the received cipher, then the result is XORed with a random number.
SERVER
‘\n’
receive_buffer
0
1
2
3
A
A
A
m = c mod n
d
DECRYPTION:

65
65
65
index

1171
22390
1953
char equivalent
10
nonce: 1234
9603
m XOR calcRandNum
encrypted
number
22327
2016
9609
9021

decrypt(cipher)

Client – Server
CLIENT
Uses the public key for encryption
Encrypted message

SERVER
Uses its private key to decrypt the message
Decrypted message
clientWindows.cpp
serverWindows.cpp
socket
socket
TCP (Transport Control Protocol)
–requires connection establishment
server uses the listen() function
server uses the accept() function

Client – Server
Server 1234
Client 127.0.0.1 1234
You should run the server first, before running the client. You can test your client and server using the same machine by using the example run above.
Sample run:
Server’s Port number for listening
Port: 1234
listening at Port 1234

CLIENT
Uses the public key for encryption
Encrypted message

SERVER
Uses its private key to decrypt the message
Decrypted message
clientWindows.cpp
serverWindows.cpp
socket
socket

Client

Reading characters from stdin
get string from stream

char* fgets(char* send_buffer, int num, FILE *stream)
reads characters from stream until (num-1) characters have been read or until it encounters:
a new line character (copied into send_buffer)
a NULL-termination character (‘\0’) is automatically appended
if an error occurs, a NULL pointer is returned

strlen() – counts the number of characters excluding the NULL-character
CLIENT
A
B
C
‘\n’
‘\0’

User entry from keyboard
strlen()=4
‘\n’
‘\0’
send_buffer
0
1
2
3
4
0
1
2
3
4
A
B
C

Define your own encryption, decryption keys
Keep in mind that the result of the encryption and decryption operations is bounded by the computed variable n.
c = m mod n
e
ENCRYPTION:
m = c mod n
DECRYPTION:
d
What are the values for p, q ?
e.g. Try this: e = 3, n = 25777, d = 16971
Aim for a relatively big number, to make the encryption and decryption results interesting.

Define your own encryption, decryption keys
c = m mod n
e
ENCRYPTION:
m = c mod n
DECRYPTION:
d
n affects the size of your valid character set.

Therefore, you need to pick your keys and nonce carefully so that all possible characters can be mapped after encryption and decryption operations.

3 Sets of encryption, decryption keys
Note: The assignment requires at least 3 sets of encryption and decryption keys.
The server should cycle through the list of encryption and decryption keys every time a new connection arrives.
c = m mod n
e
ENCRYPTION:
m = c mod n
DECRYPTION:
d

Encryption Operation
User-defined Character Set
…
space
199
#
255
^
…
253
…
0
210
2
25
1
…
100
a
b
9
c
7
62

RSA
The encryption algorithm will assign a new index number to any given character

Advanced Reading
http://www.di-mgt.com.au/rsa_alg.html#KALI93
The Handbook of Applied Cryptography
http://cacr.uwaterloo.ca/hac/

The End

C:\CORE\Massey_Papers_2016\159334-2016\159334\Demo\RSA\RSA_bignum
C:\CORE\Massey_Papers_2016\159334-2016\159334\Demo\RSA\RSA_2016\RSA_CBC_v1
RSA-CBC Testing

/docProps/thumbnail.jpeg

Related Posts