AED2025-lecture4-eng.pdf

Algorithms and Data Structures School year 2024-2025 String Processing: Encryption Summary (1st part; last lecture) String processing  Compression ◼ Encoding according to series lengths ◼ Case of text files ◼ Case of binary files ◼...

Algorithms and Data Structures School year 2024-2025 String Processing: Encryption Summary (1st part; last lecture) String processing  Compression ◼ Encoding according to series lengths ◼ Case of text files ◼ Case of binary files ◼ Encoding according to variable lengths (Huffman method) 2 Summary (2nd part) String processing  Cryptography ◼ Introduction. Fundamental concepts ◼ Caesar cipher ◼ Replacement table ◼ Vigenere cipher ◼ Vernam cipher ◼ Permutation Methods ◼ “RSA” method 3 String Processing – Compression vs. Encryption Compression Character string encoding aims to save space Encryption Character string encoding aims to keep them secret 4 String Processing – Encryption Definitions Encryption: coding of information in order to keep it secret Cryptography: Development of encryption techniques Crypto-analysis: Work associated with the task of trying to decode coded (secret) information Crypto-system: set of elements that ensure a secret means of communication between two entities 5 String Processing – Encryption Structure of a typical cryptosystem CA Communication system is insecure, ie, tamperable by CA Issuer Receiver djqtusuva.... “Strike at “Strike at dawn” dawn” Key Key Crypto-text, obtained at the expense of the original text Original and the key, through an text encryption algorithm The CA (Crypt-analyst) will know the crypto-text and the encryption method, not knowing only the key! 6 String Processing – Encryption Applications Military and diplomatic communications systems E-commerce operations Transfer of funds between banks Maintenance of secret files by users,... 7 String Processing – Encryption Methods Simple encryption methods More complex but extremely safe method – RSA Method 8 Encryption – Caesar Cipher Each character in the original text is replaced by the character that appears k positions further forward in the alphabet, where k a fixed integer (Caesar used k=3) For this purpose, the alphabet is seen as if it were organized in a circle, so that the 1st character follows the last character: character of the original text K cryptotext character 9 Encryption – Caesar Cipher Example: K=1 Original text: Crypto-text: Note: Space is the last character Weak method, since the cryptanalyst will have to analyze a reduced number of cases For example, if we have 27 characters (A, B,..., Z, space), we will only have 26 different hypotheses, 1