Assignment #2
RSA with Cipher Block Chaining (RSA‐CBC)
• TCPProtocol
• CipherBlockChaining
Copyright By PowCoder代写 加微信 powcoder
• Start‐up codes: TCP client‐server programs
16707 Client
Main components
Implement a hybrid encryption algorithm called RSA with Cipher Block Chaining for securely communicating
TCP client-server applications.
Decrypt the encrypted
Encrypted message: 23938 19210 11863 9019 plaintext message: meet me at sunset
meet me at sunset
13976 4346 22722 4827
Encrypted message: 23938 19210 11863 9019 13976 4346 22722 4827 17725 13477 21270
17725 13477 21270 11359 10558 12340
11359 10558 12340 3362 3974 10785 25372
3362 3974 10785 25372 16707
message: 23938 19210 11863 9019 13976 4346
22722 4827 17725 13477 21270 11359 10558 12340 3362 3974 10785 25372 16707
Encryption
m – plaintext message m = ‘A A A \r\n’
No regular pattern should emerge
RSA_CBC(m)12589 50082 54789 13389 59510 ciphertext
Main components
Client (sender) Server (receiver)
To reduce the complexity of the assignment, the scope is limited to one-way communication. The client is the sender of encrypted messages, and the server is the receiver
Client (sender)
Server (receiver) has a public key (e,n), and a
Main components
private key (d,n)
It is denoted as dCA(e,n), it is an encrypted public key of the server
has a certificate issued by a CA.
Client (sender) eCA – is an RSA public key
Server (receiver) has a public key (e,n), and a
Main components
nonce – to be used as part of Cipher Block Chaining
has a certificate issued by a CA. It is denoted as dCA(e,n), it is an encrypted public key of the server
private key (d,n)
Client (sender) eCA – is an RSA public key
Server (receiver) has a public key (e,n), and a
Main components
nonce – to be used as part of Cipher Block Chaining
has a certificate issued by a CA. It is denoted as dCA(e,n), it is an encrypted public key of the server
Care must be taken when assigning values to keys and nonce:
Client’s variable: nonce
Certification Authority’s keys: eCA, dCA, nCA
nCA > n nonce < n
Server’s keys: e, d, n
private key (d,n)
Sequence of steps: Client (sender)
Server (receiver)
eCA – is an RSA public key
nonce – to be used as part of Cipher
has a certificate issued by a CA. It is denoted as dCA(e,n), it is an encrypted public key of the server
Block Chaining
Key exchange
TCP connection establishment
has a public key (e,n), and a private key (d,n)
1. send certificate dCA(e,n) to client
Sequence of steps: Client (sender)
Server (receiver) has a public key (e,n), and a
eCA – is an RSA public key
nonce – to be used as part of Cipher
has a certificate issued by a CA. It is denoted as dCA(e,n), it is an encrypted public key of the server
Block Chaining
2. extract the server’s public key (e,n) using its copy of the Certification Authority’s public key.
1. send dCA(e,n) to client
eCA (dCA(e,n)) (e,n)
Key exchange
private key (d,n)
Sequence of steps:
Client (sender) eCA – is an RSA public key
Server (receiver)
nonce – to be used as part of Cipher Block Chaining
has a certificate issued by a CA. It is denoted as dCA(e,n), it is an encrypted public key of the server
2. extract the server’s public key (e,n) using its copy of the Certification Authority’s public key.
1. send dCA(e,n) to client
eCA (dCA(e,n)) (e,n)
3. Send “ACK 226 public key received”.
Key exchange
has a public key (e,n), and a private key (d,n)
Sequence of steps:
Client (sender) eCA – is an RSA public key
Server (receiver)
nonce – to be used as part of Cipher Block Chaining
has a certificate issued by a CA. It is denoted as dCA(e,n), it is an encrypted public key of the server
2. extract the server’s public key (e,n) using its copy of the Certification Authority’s public key.
1. send dCA(e,n) to client
eCA (dCA(e,n)) (e,n)
3. Send “ACK 226 public key received”. 4. Send e(nonce).
Key exchange
has a public key (e,n), and a private key (d,n)
Sequence of steps:
Client (sender) eCA – is an RSA public key
Server (receiver)
nonce – to be used as part of Cipher Block Chaining
has a certificate issued by a CA. It is denoted as dCA(e,n), it is an encrypted public key of the server
2. extract the server’s public key (e,n) using its copy of the Certification Authority’s public key.
1. send dCA(e,n) to client
eCA (dCA(e,n)) (e,n)
3. Send “ACK 226 public key received”. 4. Send e(nonce).
5. Extract the nonce using its private key, (d,n). This involves the RSA decryption operation, d(e(nonce)). Subsequently, it sends “ACK 220 nonce ok”.
Key exchange
has a public key (e,n), and a private key (d,n)
Key exchange
Sequence of steps:
Client (sender) Server (receiver)
Communication Session
Successive messages coming from the client will then be encrypted accordingly using RSA-CBC, and the server will decrypt the received messages using RSA- CBC.
Key exchange
Sequence of steps:
Client (sender) Server (receiver)
Successive messages coming from the client will then be encrypted accordingly using RSA-CBC, and the server will decrypt the received messages using RSA- CBC.
The client-server programs must be able to show the original, encrypted and decrypted messages for verification purposes.
dCA is private key of CA
TCP connection to Port 1024
eCA is public key of CA (this key is known by the client)
established
RSA with CBC
Send encrypted public key: dCA(e, and n) dCA is private key of CA
• Receive encrypted public key: dCA(e, and n)
• send ACK
• decrypt keys: eCA(dCA(e,n))
Receive e(nonce) Extract nonce: d(e(nonce)) nonce must be < n
• Send e(nonce).
This is a number that is used only once
send ACK nonce
• get user input (message)
• Receive encrypted message
• Decrypt message using RSA with
• Use RSA with CBC (e, n, nonce) to encrypt message:
CBC (d, n, nonce)
• display original message
• display decrypted message
• (optional) echo back the
• Send encrypted message
decrypted message
time • (optional) display received message
Passive open
Active open
• Generate nonce
• Use public key to encrypt nonce: e(nonce)
Demonstration
Decrypted server’s public key (e,n)=(737, 67637)
Encrypted server’s public key dCA(e,n)=(51177, 42697)
Demonstration
CLIENT SERVER
Encrypted nonce:
decrypted nonce
e(nonce) = 16150
nonce=1234
Demonstration
CLIENT SERVER
RSA: Choosing keys
1. Choose two large prime numbers p, q. (e.g., 1024 bits each)
2.Computen=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.
(inotherwords:edmodz =1).
5. Public key is (e, n). Private key is (d, n).
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
RSA: Encryption, decryption
0. Given a public key (e, n) and a private key (d, n) 1. To encrypt bit pattern, m, compute
c = m mod n (i.e., remainder when m is divided by n) 2. To decrypt received bit pattern, c, compute
(i.e., remainder when c is divided by n)
Magic happens!
m = (memod n)d mod n
c m = c mod n
m c=m mod n
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).
cd = 481968572106750915091411825223072000 - too big !! (int type)
How to solve this problem:
Repeated Squaring: calculate y = x e mod n
long repeatSquare(long x, long e, long n) {
c = me mod n m = cd mod n
y=1;//initialize y to 1, very important while (e > 0) {
if (( e % 2 ) == 0) {
x = (x*x) % n;
e = e/2; }
Use repeatSquare for both encryption and decryption. You might want to change the datatypes used in this function to accommodate bigger numbers in the encryption scheme.
y = (x*y) % n;
return y; //the result is stored in y }
Check if e & z are coprimes.
Euclidean Algorithm gcd(e,z): Extended Euclidean Algorithm
Summary of Techniques
RSA public key (e, n) and a private key (d, n)
Solve for d
zx + ed = gcd(z,e)=1
Bézout’s identity.
It’s not very difficult to implement both Algorithms for automatically generating the RSA keys.
Example of RSA keys 1024‐bit RSA encryption key (in hex format):
n= A9E167983F39D55FF2A093415EA6798985C8355D9A915BFB1D01DA197026170F
BDA522D035856D7A986614415CCFB7B7083B09C991B81969376DF9651E7BD9A9 3324A37F3BBBAF460186363432CB07035952FC858B3104B8CC18081448E64F1C FB5D60C4E05C1F53D37F53D86901F105F87A70D1BE83C65F38CF1C2CAA6AA7EB
d= 67CD484C9A0D8F98C21B65FF22839C6DF0A6061DBCEDA7038894F21C6B0F8B35 DE0E827830CBE7BA6A56AD77C6EB517970790AA0F4FE45E0A9B2F419DA8798D6 308474E4FC596CC1C677DCA991D07C30A0A2C5085E217143FC0D073DF0FA6D14 9E4E63F01758791C4B981C3D3DB01BDFFA253BA3C02C9805F61009D887DB0319
https://www.boost.org/ http://www.di‐mgt.com.au/rsa_alg.html#realexample range
You need a big number library, like Boost to implement values at this
Sample Small Keys
p=257 and q=293
e=529; d=24305; n=75301;
Use keys at least around the following range of values. Remember, the bigger the keys, the better! However, you need to make sure that the data type you are using can accommodate the range of values for which the algorithm will be operating on.
Review of CBC
Given the binary representation of a plain text message (m), compute for its cipher text using CBC. Assume that the message is processed in blocks of 3 bits, and that the initial random number is equal to 010. Fill-up the following table with the details of your solution.
m = 110110110 1) ENCRYPTION
Table representing Ks()
INFO. TO SEND
i m(i) r(i) c(i)
Put initial random number as the value for r(1)
Review of CBC
Given the binary representation of a plain text message (m), compute for its cipher text using CBC. Assume that the message is processed in blocks of 3 bits, and that the initial random number is equal to 010. Fill-up the following table with the details of your solution.
m = 110110110 1) ENCRYPTION
Table representing Ks()
INFO. TO SEND
i m(i) r(i) c(i)
110 110 110
Split the original plaintext message into blocks of 3-bits
Review of CBC
Given the binary representation of a plain text message (m), compute for its cipher text using CBC. Assume that the message is processed in blocks of 3 bits, and that the initial random number is equal to 010. Fill-up the following table with the details of your solution.
m = 110110110 1) ENCRYPTION
Table representing Ks()
c(i) 011 INFO. TO
Solve for c(1):
110 110 110
Review of CBC
Given the binary representation of a plain text message (m), compute for its cipher text using CBC. Assume that the message is processed in blocks of 3 bits, and that the initial random number is equal to 010. Fill-up the following table with the details of your solution.
m = 110110110 1) ENCRYPTION
Table representing Ks()
c(i) INFO. TO SEND
110 110 110
The next random number block is equal to the previous cipherblock, C(1). Therefore, copy c(1) onto r(2).
Review of CBC
Given the binary representation of a plain text message (m), compute for its cipher text using CBC. Assume that the message is processed in blocks of 3 bits, and that the initial random number is equal to 010. Fill-up the following table with the details of your solution.
m = 110110110 1) ENCRYPTION
Table representing Ks()
c(i) INFO. TO SEND
Compute for c(2).
110 110 011
Review of CBC
Given the binary representation of a plain text message (m), compute for its cipher text using CBC. Assume that the message is processed in blocks of 3 bits, and that the initial random number is equal to 010. Fill-up the following table with the details of your solution.
m = 110110110 1) ENCRYPTION
Table representing Ks()
c(i) INFO. TO SEND
011 010 011 010 011
110 110 110
Continue until we have computed all the cipher blocks. Message to send: = 010 011 010 011
Review of CBC
2) DECRYPTION
Using your answer in Item#1 (information to send), decrypt the message using CBC. Fill-up the table with the details of your solution.
Table representing Ks()
Encrypted message = 010 011 010 011
i c(i) r(i) Ks(c(i)) m(i)
011 110 110
Review of CBC
2) DECRYPTION
Using your answer in Item#1 (information to send), decrypt the message using CBC. Fill-up the table with the details of your solution.
Table representing Ks()
Encrypted message = 010 011 010 011
Compute for m(1).
i c(i) r(i)
Ks(c(i)) 100 m(i) 110
011 110 110
Review of CBC
2) DECRYPTION
Using your answer in Item#1 (information to send), decrypt the message using CBC. Fill-up the table with the details of your solution.
Table representing Ks()
Encrypted message = 010 011 010 011
i c(i) r(i)
Ks(c(i)) 100
100 110 110
Compute for m(2) and m(3) following a similar strategy.
011 110 110
• Combination of Public key and Symmetric key cryptography
• 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.
• No need for any mini-table mapping of plaintext to ciphertext.
RSA with Cipher Block Chaining
Plaintext message
Server’s PUBLIC_KEY: (3, 25777) Initial NONCE: 1234
m = ‘AAA\n’
Encryption Example
RSA_CBA Encryption
Encryption is performed on the index number of the character XORed with a
random number.
c = me mod n PUBLIC_KEY: (3, 25777)
NONCE: 1234
User entry index Similar to CBC m XOR calcRandNum
ENCRYPTION:
encrypt(m XOR calcRandNum)
send_buffer
RSA_CBA Encryption
Encryption is performed on the index number of the character XORed with a
random number.
c = me mod n PUBLIC_KEY: (3, 25777)
User entry
Similar to CBC
NONCE: 1234
65 xor 1234 = 1171
ENCRYPTION:
m XOR calcRandNum 1171
encrypt(m XOR calcRandNum)
send_buffer
RSA_CBA Encryption
Encryption is performed on the index number of the character XORed with a
random number.
NONCE: 1234
c = me mod n PUBLIC_KEY: (3, 25777)
User entry
index Similar to CBC m XOR calcRandNum
65 1171 A2 65
ENCRYPTION:
encrypt(1171) using the PUBLIC_KEY: (3, 25777)
This is implemented by calling repeatSquare(1171, 3, 25777) = 22327
encrypt(m XOR calcRandNum)
send_buffer
RSA_CBA Encryption
Encryption is performed on the index number of the character XORed with a
random number.
NONCE: 22327
c = me mod n PUBLIC_KEY: (3, 25777)
User entry
index Similar to CBC m XOR calcRandNum
65 1171 A2 65
ENCRYPTION:
NONCE is updated to 22327 (the most recent cipher block computed).
encrypt(m XOR calcRandNum)
send_buffer
RSA_CBA Encryption
Encryption is performed on the index number of the character XORed with a
random number.
NONCE: 22327
c = me mod n PUBLIC_KEY: (3, 25777)
User entry
index Similar to CBC m XOR calcRandNum
1953 9609 9603 9021
ENCRYPTION:
65 1171 22327 22390 2016
Continuing with the same sequence of operations, we get the complete ciphertext.
encrypt(m XOR calcRandNum)
send_buffer
RSA_CBA Encryption
Encryption is performed on the index number of the character XORed with a
random number.
NONCE: 22327
c = me mod n PUBLIC_KEY: (3, 25777)
User entry
index Similar to CBC m XOR calcRandNum
22327 1953 9609
\n send_buffer
ENCRYPTION:
22390 2016
The client then sends the following ciphertext concatenated with some delimeters to the server.
encrypt(m XOR calcRandNum)
RSA with Cipher Block Chaining
Server’s PRIVATE_KEY: (16971, 25777) Initial NONCE: 1234
Decryption Example
c = 22327 2016 9606 9021 \r\n
RSA_CBA Decryption
Decryption is performed on the received cipher, then the result is XORed with a
random number.
DECRYPTION:
m = cd mod n PRIVATE_KEY: (16971, 25777)
NONCE: 1234 cipher
22327 2016 9609 9021 \r
Trim off the delimeters from the input.
receive_buffer
decrypt(cipher)
m XOR calcRandNum
char equivalent
RSA_CBA Decryption
Decryption is performed on the received cipher, then the result is XORed with a
random number.
DECRYPTION:
m = cd mod n PRIVATE_KEY: (16971, 25777)
NONCE: 1234 cipher
receive_buffer
decrypt(cipher)
m XOR calcRandNum
Decrypt(22327) using the Server’s PRIVATE_KEY: (16971, 25777) This is implemented by calling repeatSquare(22327, 16971, 25777) = 1171
char equivalent
RSA_CBA Decryption
Decryption is performed on the received cipher, then the result is XORed with a
random number.
DECRYPTION:
m = cd mod n PRIVATE_KEY: (16971, 25777)
NONCE: 1234 cipher
receive_buffer
decrypt(cipher)
m XOR calcRandNum
1171 xor NONCE = 1171 xor 1234 = 65
char equivalent
RSA_CBA Decryption
Decryption is performed on the received cipher, then the result is XORed with a
random number.
DECRYPTION:
m = cd mod n PRIVATE_KEY: (16971, 25777)
NONCE: 1234 cipher
receive_buffer
decrypt(cipher)
m XOR calcRandNum
65 is the ASCII code for the letter ‘A’.
char equivalent
RSA_CBA Decryption
Decryption is performed on the received cipher, then the result is XORed with a
random number.
DECRYPTION:
m = cd mod n PRIVATE_KEY: (16971, 25777)
NONCE: 22327 cipher
receive_buffer
decrypt(cipher)
m XOR calcRandNum
NONCE is then set to 22327 (the previous cipher block).
This will ensure that any repeating characters in the input will not generate any repeating patterns in the ciphertext.
char equivalent
RSA_CBA Decryption
Decryption is performed on the received cipher, then the result is XORed with a
random number.
DECRYPTION:
m = cd mod n PRIVATE_KEY: (16971, 25777)
NONCE: 1234 cipher
22390 65 A1
1953 65A2 9603 10 ‘\n’ 3
receive_buffer
decrypt(cipher)
m XOR calcRandNum
char equivalent
Continue with the decryption process until all plaintext characters have been extracted.
7 Extra work done (Max. bonus of 2 Program uses the Boost library’s big
number facility. Very large public key and
private keys are being used.
Include instructions on how to install the big number library you used and the compilation instructions.
Write CA’s large Public key: Write CA’s large Private key: Write Server’s large Public key: Write Server’s large Private key:
Reading characters from stdin
get string from stream
char* fgets(char* send_buffer, int num, FILE *stream)
• reads characters from stream until (num‐1
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com