CS计算机代考程序代写 chain information theory algorithm 2. Cryptography 1 – Encryption Decryption

2. Cryptography 1 – Encryption Decryption

Cryptography 1:
Encryption Decryption

Alvaro Monsalve
alvaro. .au

CITS3004

1

1. Cryptology Concepts
2. Classical Ciphers
3. Product Ciphers with Symmetric Key
4. Encryption Modes (Algorithms)
5. Cryptanalysis

Sections

2

Cryptology is the study of cryptographic techniques
and analysis of systems

3

1. Cryptology

Cryptology

Cryptography

Private-key
Cryptography

Public-key
Cryptography

Protocols

Cryptanalysis

Source: Prof. Baktier’s lecture at WPI

Cryptography
– To keep information safe from adversaries

Cryptanalysis
– Understanding the mechanisms of cryptography

4

Cryptology

We will look at ciphers of cryptography

5

Cryptography

Cryptology

Cryptography

Private-key
Cryptography

Public-key
Cryptography

Protocols

Cryptanalysis

Plaintext (P)
– Original message – “this is a secret message”

Ciphertext (C)
– Encrypted message – “dlgc mq k wcmvcd qccwyqi”

Cipher (algorithms)
– Algorithm or set of instructions for converting plaintext to ciphertext, and vice versa. – Caesar,

Vigenere, DES, AES, TWOFISH etc.
Key(s) (K)

– Secret information to correctly operate the ciphers
– Can be the same for encryption/decryption (symmetric), or different ones (asymmetric).

Encrypt E(P)
– Converting the plaintext into a ciphertext

Decrypt D(C)
– Recovering the plaintext from a ciphertext

6

Basic Terminologies

Using Vigenere cipher with key “key” from https://planetcalc.com/2468/

7

Basic Terminology

Sender Receiver

Encryption
algorithm

Decryption
algorithm

plaintext ciphertext plaintext

symmetric key cipher

Bob’s public key Bob’s private key

fdafieoa

jfvhlfjea

asymmetric key cipher

AES, DES etc…

RSA etc…

• The principle of ciphers is to use both substitution
and transposition
– Proved by C.E. Shannon
– Using information theory in 1945

• Formulate the principles of “ ” and
“ ”.

8

Principle of Ciphers

confusion
diffusion

• Confusion
– Through transposition/permutation
– Changing the plaintext order

• Diffusion
– Through substitution
– Replacing plaintext with ciphertext

9

Principle of Ciphers

• Transposition (permutation)
– Plaintext: This is some secret message
– Ciphertext: hTsi si osem esrcte emssgae

• Substitution
– Plaintext: This is some secret message
– Ciphertext: Xduq uq qzvl qlrklx vlqqmyl

10

Principle of Ciphers

1. Classical Encryption techniques
• Caesar cipher
• Mono alphabetic cipher
• Vigenere cipher
• Transposition cipher

2. Modern ciphers
• Product ciphers

• DES, AES etc.

11

2. Ciphers

• Typically uses either substitution or transposition
only.

• Substitution ciphers further divide into
monoalphabetic and polyalphabetic

12

Classical Ciphers

• Earliest known substitution cipher
• By Julius Caesar
• Replace each letter by the ith letter

13

Caesar Cipher

Key = i

• Given the secret message:
– P : hello world!
– K : 10
– i.e., ‘a’ becomes ‘k’

• What is the ciphertext using Caesar cipher?
• How to decrypt?

14

Caesar Cipher

A: rovvy gybvn

C = E(P) = P + K mod 26

P = D(C) = C – K mod 26

• Modular operations example
• If 6 hours pass, what time is it?
• 13? No (not on this clock)

• 7 + 6 mod 12 ≡ 1

15

Caesar Cipher

• New Clock: Caesar clock
– Modulus 26 using English

16

Caesar Cipher

A B C D … Y Z

0 1 2 3 … 24 25

We will cover more mod operations later in RSA next week

• Cipher is known (i.e., Caesar cipher)
• Key is unknown
• Task: Retrieve the plaintext

• Found the plaintext? You just did a brute-force attack!

17

Class exercise

C: uijt jt b tfdsfu

Q: How long will it take to brute-force?

P: This is a secret

• Why is it so weak?
– A: The key size is too small (25)

• What can we do to improve this?
– A: use a mono alphabetic cipher that uses an arbitrary

substitution

18

Caesar Cipher

Shuffling the letters in the plaintext by
mapping them to a different random
ciphertext letter

• Setup a secret key phrase (or a word)
– Secret key: MARKET

• The rest alphabet letters follows the last character
– E.g., T is the last letter in our secret key

• Remaining alphabets appended at the end in order
– Excluding ones already used in the secret key

19

Mono Alphabetic Cipher

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

M A R K E T U V W X Y Z B C D F G H I J L N O P Q S

20

Mono Alphabetic Cipher

What are some commonly
used letters?

21

Mono Alphabetic Cipher

• Here is an example.

• Frequency computation result

SLAAP UNAOL NVVKZ ABMMP UDOPS LRLLW PUNAO LIHKZ ABMMV BAPZA
OLJYP APJHS WYVIS LTAOH AHUFJ VTWBA LYMPY LDHSS ULLKZ AVZVS
CLPAO HZAVH JAHZN HALRL LWLYP AOHZA VMPNB YLVBA DOPJO IPAZH
YLOHY TMBSH UKKLU FAOLT LUAYF PAOHZ AVKVA OPZDP AOVBA BUYLH
ZVUHI SFKLS HFPUN AYHMM PJ

A: 29 B: 9 C: 1 D: 4 E: 0 F: 5 G: 0 H: 18 I: 4 J: 6 K: 7 L: 24 M: 9 N: 6
O: 14 P: 18 Q: 0 R: 2 S: 10 T: 4 U: 11 V: 14 W: 4 X: 0 Y: 11 Z: 12

22

Vigenere Cipher

• Mono alphabetic cipher fails to hide the frequency
information.

• To address this issue, we use a series of different
Caesar ciphers.

• This is called polyalphabetic cipher
• A popular example is the Vigenere Cipher

(Vee-gee-nee-er)

23

P: WE HACK AT NOON
K: PAID

C: LE PDRK IW COWQ

Polygram substitution

To do: Encrypt the message.

24

Vigenere Cipher

• How to break?! Cannot perform frequency analysis anymore
• Kasiski Examination (1863): There is a chance that a repeated

word is encrypted using the same sequence of the key

• There are more substitution ciphers.

C R Y P T O I S S H O R T F O R C R Y P T O G R

A B C D A B C D A B C D A B C D A B C D A B C D

C S A S T P K V S I Q U T G Q U C S A S T P I U

P

K

C

25

Transposition Cipher

• The aim is to hide the message by rearranging the
letters without altering the original letters

• These ciphers are prone to frequency analysis attacks
• For example: Rail fence cipher (or zigzag cipher)

26

Rail Fence Cipher

• Arrange the plaintext in N dimensions in a zigzag
style

• Recollect the letters in straight lines to formulate the
ciphertext
– E.g., 2 dimension (N = 2)
– P: THE ANSWER IS ELEVEN
– C: TENWRSLVNHASEIEEE
– You can do it multiple rounds!

T E N W R S L V N

H A S E I E E E

• Classical ciphers are not so secure
today due to the limited key size
and also language characteristics

• To improve the security of ciphers,
both substitution and transposition
techniques are used together

27

Classical Ciphers summary

substitution &
transposition

• Which one is more secure?
– Substitution twice
– Transposition twice
– Substitution and then transposition

28

3. Modern Ciphers

In General, we call these product ciphers

29

Classification of
Encryption algorithms

Encryption algorithms

Symmetric key

Block

Feistel SPN etc

Stream

random Pseudo-random

Asymmetric key

Later…

DES AES

64 bits, 128 bits etc 1 bit (or byte)

30

Stream Cipher

Pseudo-random
sequence generation

Plaintext
bitstream

Ciphertext
bitstream

Key

Operation (e.g., XOR)

Plaintext bitstream 111111110000……
Pseudo-random stream 100101110100……
Ciphertext stream 011010000100……

Plaintext

31

Block Cipher

Block
cipher

K bits Key

n bit
ciphertext

n bits n bits n bits n bits x bits padding

n bits

Block ciphers have different operation modes:
ECB, CBC, OFB, CFB, CTR (coming soon)

Stream Block

Pros.
• Speed of transformation
• Low error propagation

• High diffusion
• Immunity to insertion of symbols

Cons.
• Low diffusion
• Susceptible to malicious insertion

and modification

• Slow
• Error propagation

32

Stream vs Block
SecurityPerformance

• DES – Data Encryption Standard
• Block cipher
• 64bits plaintext
• 64 bits key (56 bits key + 8 bits parity)
• 64 bits ciphertext

33

DES

• 16 rounds
• S and P boxes each

round

34

DES

For more details, see additional items.

• 56 bit key is too short(!)
• We can brute force it with today’s computers

– Takes roughly 256 trials.
– Typical CPU today would still take 100+ years
– But we can also parallelise the process, as well as exploit the algorithms

• 1997: DESCHALL Project (parallel computing) -> 96 days
• 1998: EFF’s DES cracker -> 56 hours
• 1999: DES cracker + distributed.net -> 22 hours
• 2017: chosen-plaintext attack with rainbow table* -> 25 seconds!

35

DES: Security concern

*A rainbow table is a listing of all possible plaintext permutations of encrypted passwords specific to a given hash algorithm.

• To overcome this problem, NIST published Advanced
Encryption Standard (AES) in 2001
– The AES competition included RC6, Serpent, MARS, and Twofish

• But we built software and hardware for DES
• Let us not waste it

– Solution: lets use DES multiple times!

36

DES: Security concern

But how many times?

• 2-DES: C = EK2(EK1(P))
• So, X = EK1(P) = DK2(C)
• Given a known pair (P, C), attack as follows:
– Encrypt P with all 256 possible keys for K1
– Decrypt C with all 256 possible keys for K2
– If EK1’(P) = DK2’(C), try the keys on another (P*, C*)
– If works, it is highly likely that (K1’, K2’) = (K1, K2)

37

DES Twice!

Q:How much did it improve from 1-DES?

• Let us triple the DES:
• In practice, C = EK3(DK2(EK1(P))) (a.k.a. EDE encryption)
• How many keys do we need?

38

Triple DES

2 (or 3)
K3 = K1 would result in a totally different C
(i.e., works with only 2 keys)
If K1 = K2 = K3, then it is equivalent to 1-DES.
This means Triple DES can be used as 1-DES as well.

• We can use meet-in-the-middle attack on 3DES
– Requires known pair of (A, C)

1. Encrypt P, producing value A
2. Using A and C, attack 2DES (i.e., slide 37)

• This attack takes (256 x 256) = O(2112) steps

39

Triple DES: Lets attack it

E

E

D

P

C

K1

K2

K1

A

B

Assuming a 64 bit key, you would require 100 million
computers with 1.6TB hard drive to carry this out

• Triple DES has been implemented into some internet
applications
– Such as PGP (pretty good privacy) and S/MIME

(Secure/Multipurpose Internet Mail Extensions)

• But! Triple DES is too slow
• Let us have a look at its successor – AES

40

Triple DES downfall

• Advanced Encryption Standard
• Block length of 128 bits (fixed)
• Key size varies 128, 192 or 256 bits
• Number of rounds are 10, 12 and 14 respectively to

the key size.

41

AES: ADVANCED
ENCRYPTION STANDARD

42

AES

• Four functions are used each round
– ByteSub (nonlinear layer)
– ShiftRow (linear mixing layer)
– MixColumn (nonlinear layer)
– AddRoundKey (key addition layer)

• Currently no practical exploits
– 2126 operations needed to break 128 bits key size AES (2015)
– Other approach includes side channel attacks (covered later)

43

AES

Animation (YouTube video) in the additional items

• DES, Triple DES, AES <- all block ciphers. • Need some way to encrypt/decrypt arbitrary amounts of data in practice • 5 common modes are defined for AES and DES – ECB: Electronic Code Book – CBC: Cipher Block Chaining – CFB: Cipher Feed Back – OFB: Output Feed Back – CTR: Counter 44 4. Encryption Modes • Message is broken into independent blocks • Each block is encrypted independently • If two same messages are encrypted using the same key and sent, their ciphertexts are the same – E.g., Sending your personal information. • Should only be used to transmit single values. 45 ECB: Electronic Code Book 46 ECB Encrypt P1 C1 K Encrypt P2 C2 K Encrypt Pn Cn K… Decrypt C1 P1 K Decrypt C2 P2 K Decrypt Cn Pn K… • Can be parallelised but… • Due to the design, message repetitions may show in the ciphertext – Particularly with data such as graphics – Messages that change very little etc. • The independence between the encrypted messages is the problem 47 ECB 48 ECB Original ECB • Removes the independence between message blocks – By linking the encryption operations – i.e., next ciphertext depends on the previous ciphertext • Establish an Initial Vector (IV) to start the process • Can be used for general transmission of block ciphers – E.g., IPSec using 3DES-CBC, AES-CBC 49 CBC: Cipher Block Chaining 50 CBC … … Encrypt P1 C1 K IV Encrypt P2 C2 K Encrypt Pn Cn K Decrypt C1 P1 K IV Decrypt C2 P2 K Decrypt Cn Pn K • A ciphertext block depends on all the previous blocks – i.e., no repetitions of the same plaintext • Requires the Initialisation Vector (IV) – Must be known to both sender and receiver – Can be a fixed value (with an integrity guarantee), or – Sent encrypted (e.g., using the ECB mode) • Error propagation problem 51 CBC 52 CBC Decrypt C1 P1 K IV Decrypt C2 P2 K Decrypt C3 P3 K Decrypt C4 P4 K Broken Affected 53 ECB vs CBC Original ECB CBC • To use the cipher block of the previous step as the input of the cipher in the next step • Divide the plaintext into segments of length s bits – S ≤ block size • Encryption is used to generate a sequence of keys of length s bits • The ciphertext is produced by XOR operation of the plaintext and the key 54 CFB: Cipher Feed Back 55 CFB … Encrypt C1 P1 Decrypt IV P1 K C1 Decrypt C2 P2 K … Decrypt Cn Pn K Encrypt C2 P2 Encrypt Cm Pn K IV K K • The block cipher is used as a stream cipher • Used in scenarios where data arrives in bits/bytes – Common value for s is 8 bits – The bit can be as small as 1, denoted as CFB-[bit size] • Similarly with CBC, the ciphertext depends on the all previous plaintext 56 CFB 57 CBC vs CFB Encrypt P1 C1 K CBC Encrypt C1 P1 CFB CBC performs XOR first with the plaintext before encryption CFB performs XOR with the plaintext after encryption K • Message is treated as stream of bits • Output of the cipher is added to the message • Output is used for the next cipher step (feed back) • Feedback is independent of message – i.e., can be computed in advance • Can be used to encrypt stream of messages on a noisy channel – E.g., satellite TV transmission etc 58 OFB: Output Feed Back 59 OFB …DecryptIV P1 K C1 Decrypt C2 P2 K … Decrypt Cn Pn K Encrypt C1 P1 Encrypt C2 P2 Encrypt Cn Pn IV K KK • No bit error propagation • More vulnerable to message stream modification • Should never reuse the same sequence of key and IV – Because it generates the same ciphertext! • Requires synchronisation between the sender and the receiver – But this is more related to computer networks – see CITS3002 60 OFB OFB is a variation of a Vernam cipher, which XOR the plaintext with a random stream of data of the same length • Relatively new compared to other four • Similar to OFB but encrypts the counter value instead of the feedback value • Requires different keys and counter values for every plaintext block • Used in high-speed network encryptions 61 CTR: Counter 62 CTR …DecryptNonce + Counter (1) P1 K C1 Encrypt Nonce + Counter (1) C1 P1 K Encrypt Nonce + Counter (2) C2 P2 K Encrypt Nonce + Counter (n) Cn Pn K… Decrypt Nonce + Counter (2) P2 K C2 Decrypt Nonce + Counter (n) Pn K Cn 63 OFB vs CTR Encrypt C1 P1 Encrypt Nonce + Counter (1) C1 P1 K IV is replaced with Nonce and counter combination No more feedback operations in CTR OFB CTR IV K • A counter is initialised in addition to a nonce • The counter is incremented by 1 for each block • For example, 128 bits (16 bytes) 64 CTR Initial 24 49 E3 7A 83 1B 74 9A 00 00 00 00 00 00 00 01 Counter 2 24 49 E3 7A 83 1B 74 9A 00 00 00 00 00 00 00 02 Counter 3 24 49 E3 7A 83 1B 74 9A 00 00 00 00 00 00 00 03 Counter 4 24 49 E3 7A 83 1B 74 9A 00 00 00 00 00 00 00 04 Nonce Counter • Fast encryption decryption – E.g., parallel computation • Random access to encrypted data blocks – i.e., no feedback • Provable security (as good as other modes) 65 CTR • ECB – Electronic Code Book • CBC – Cipher Block Chaining • CFB – Cipher Feed Back • OFB – Output Feed Back • CTR – Counter 66 Block Cipher Modes summary Don’t use Most popular Fast Use CTR instead • Cryptology is the study of cryptographic techniques and the analysis. 67 Cryptology Cryptology Cryptography Private-key Cryptography Public-key Cryptography Protocols Cryptanalysis Source: Prof. Baktier’s lecture at WPI • Objective to recover key not just message • General approaches – Brute force attack – Cryptanalytic attack 68 5. Cryptanalysis • To try every possible way • Simple to develop the procedure • Success rate proportional to the key size • Assume known or recognised plaintext 69 Brute Force attack Key size (bits) No. of keys 1 decryption/µs 106 decryptions/µs 32 232 = 4.3 x 109 35 minutes 2 ms 56 256 = 7.2 x 1016 1142 years 10 hours 128 2128 = 3.4 x 1038 5.4 x 1024 years 5.4 x 1018 years 168 2168 = 3.7 x 1050 5.9 x 1036 years 5.9 x 1030 years 26 characters 26! = 4 x 1026 6.4 x 1012 years 6.4 x 106 years AMD Ryzen Threadripper 3990X : 2,356,230 IPS/µs at 4.35 GHz But, 1 decryption > 1 instruction

https://en.wikipedia.org/wiki/Ryzen

• Ciphertext only
– Only knows the algorithm and ciphertext

• Known plaintext
– Knows the plaintext & ciphertext

• Chosen plaintext
– Select plaintext and obtain ciphertext

• Chosen ciphertext
– Select ciphertext and obtain plaintext

• Chosen text (combination of the above two)
– Select plaintext or ciphertext to encrypt/decrypt

70

Cryptanalytic Attacks

Known to attacker C1, C2, …, Cn

Objective

1) P1, P2, …, Pn
2) Key K

3) Algorithm Cn+1 -> Pn+1

71

Cryptanalytic Attacks

Ciphertexts
generated using the

same key

Find an algorithm that can
decrypt any message

encrypted using the key K

• Ciphertext only

• Known plaintext

72

Cryptanalytic Attacks

Known to attacker (P1, C1), (P2, C2), …, (Pn, Cn),

Objective
1) Key K

2) Algorithm Cn+1 -> Pn+1

Attacker cannot
select these pairs

• Chosen plaintext

73

Cryptanalytic Attacks

Known to attacker (P1, C1), (P2, C2), …, (Pn, Cn),

Objective
1) Key K

2) Algorithm Cn+1 -> Pn+1

Attacker can select
the plaintext before
attack begins, and

cannot gain
additional pair after
the attack started.

• Chosen ciphertext

74

Cryptanalytic Attacks

Known to attacker (P1, C1), (P2, C2), …, (Pn, Cn),

Objective
1) Key K

2) Algorithm Cn+1 -> Pn+1

Attackers can select
ciphertexts before
the attack begins

This attack exploits public key algorithm, as attackers can
generate ciphertexts using the public key

• Total break
– Found the key

• Global deduction
– Did not find the key, but found the algorithm

• Instance deduction
– Obtained some plaintexts from some ciphertexts

• Information deduction
– Obtained partial bits of plaintext

75

Result of attacks

• Computationally secure
– Cost to break is higher than cost to encrypt
– Time taken exceeds the useful lifetime

• Probably secure
– The security mechanism can be proven to be equivalent to a hard

problem
• Unconditional security

– The attacker cannot succeed in cryptanalysing the algorithm given an
infinite amount of resources

76

Secureness of ciphers

• We covered various classical ciphers
– Caesar, mono alphabetic, Vigenere and Rail Fence

• We covered modern ciphers
– DES, Triple DES and AES

• Details of block cipher modes
• Cryptanalysis overview

77

Summary

• Cryptography 2: RSA and DH
– Plus hashing and Blockchain

78

Next Week

1. https://en.wikipedia.org/wiki/Instructions_per_secon
2. DES details

– https://www.tutorialspoint.com/cryptography/data_encryption_standard.
htm

3. AES encryption animation (mind the music)
– https://www.youtube.com/watch?v=evjFwDRTmV0

4. Block Cipher Modes
– http://www.crypto-it.net/eng/theory/modes-of-block-ciphers.html

5. Image From:
– https://pixabay.com/photos/bitcoin-mining-processor-3369039/

79

References

https://en.wikipedia.org/wiki/Instructions_per_secon
https://www.tutorialspoint.com/cryptography/data_encryption_standard.htm

http://www.crypto-it.net/eng/theory/modes-of-block-ciphers.html
https://pixabay.com/photos/bitcoin-mining-processor-3369039/