logging in or signing up Anthony Zanontian - Cryptography anthony.zanontian Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 647 Category: Education License: All Rights Reserved Like it (0) Dislike it (0) Added: March 10, 2009 This Presentation is Public Favorites: 1 Presentation Description No description available. Comments Posting comment... By: anand13 (10 month(s) ago) good plz give it Saving..... Post Reply Close Saving..... Edit Comment Close By: muthukumar852 (14 month(s) ago) gppd Saving..... Post Reply Close Saving..... Edit Comment Close By: nagarakhilesh (14 month(s) ago) pls send me... Saving..... Post Reply Close Saving..... Edit Comment Close By: gazalshabab (15 month(s) ago) plz send this ppt on my email id gazal_shabab@yahoo.com Saving..... Post Reply Close Saving..... Edit Comment Close By: kakerot (26 month(s) ago) HEY BUDDY .. THE PRESENTATION IS AWESOME. I NEED IT . IF POSSIBLE PLEASE SEND IT TO ME... MY ID IS:- rayovania@gmail.com... damn good work.. seriously hoping to get ur ppt... thank you Saving..... Post Reply Close Saving..... Edit Comment Close Premium member Presentation Transcript Cryptography : 04/03/29 1 Cryptography Kevin O’Bryant kobryant@ucsd.edu www.math.ucsd.edu/~kobryant Math 187 MWF 4:00 – 4:50 pm www.math.ucsd.edu/~crypto Definitions : 04/03/29 2 Definitions Plaintext The message that Alice wants Bob to read Ciphertext The message that Alice sends Bob Cryptosystem The algorithm that Alice uses to turn plaintext into ciphertext. Key Something Bob and Alice agree on beforehand that customizes the cryptosystem Cryptosystems : 04/03/29 3 Cryptosystems Two basic types: Substitution (replace letters) Transposition (rearrange letters) Caeser Cipher Shift each letter by the same amount Key: how much to shift Monoalphabetic Substitution Replace each letter with some other letter in a one-to-one manner Key: the bottom line of Plaintext: abcdefghijklmnopqrstuvwxyz Ciphertext: QWERTYUIOPASDFGHJKLZXCVBNM Caeser Cipher : 04/03/29 4 Caeser Cipher GZO PN OCZMZAJMZ WMVXZ JPMNZGQZN OJ JPM YPOT, VIY NJ WZVM JPMNZGQZN, OCVO DA OCZ WMDODNC ZHKDMZ VIY DON XJHHJIRZVGOC GVNO AJM V OCJPNVIY TZVMN, HZI RDGG NODGG NVT, 'OCDN RVN OCZDM ADIZNO CJPM.‘ Caeser Cipher Strengths Very Fast Easy to remember Cipher Wheels : 04/03/29 5 Cipher Wheels Caeser Cipher : 04/03/29 6 Caeser Cipher GZO PN OCZMZAJMZ WMVXZ JPMNZGQZN OJ JPM YPOT, VIY NJ WZVM JPMNZGQZN, OCVO DA OCZ WMDODNC ZHKDMZ VIY DON XJHHJIRZVGOC GVNO AJM V OCJPNVIY TZVMN, HZI RDGG NODGG NVT, 'OCDN RVN OCZDM ADIZNO CJPM.‘ Caeser Cipher Strengths Very Fast Easy to remember Weaknesses Formatting gives away the house Small number of keys: 26 (and one is weak) Frequency analysis Strengthening Caeser : 04/03/29 7 Strengthening Caeser Fixing the Formatting Weakness Strip out punctuation, and put letters in blocks of the same length. GZO PN OCZMZAJMZ WMVXZ JPMNZGQZN OJ JPM YPOT, VIY NJ WZVM JPMNZGQZN, OCVO DA OCZ WMDODNC ZHKDMZ VIY DON XJHHJIRZVGOC GVNO AJM V OCJPNVIY TZVMN, HZI RDGG NODGG NVT, 'OCDN RVN OCZDM ADIZNO CJPM.‘ becomes GZOP NOCZ MZAJ MZWM VXZJ PMNZ GQZN OJJP MYPO TVIY NJWZ VMJP MNZG QZNO CVOD AOCZ WMDO DNCZ HKDM ZVIY DONX JHHJ IRZV GOCG VNOA JMVO CJPN VIYT ZVMN HZIR DGGN ODGG NVTO CDNR VNOC ZDMA DIZN OCJP M Strengthening Caeser : 04/03/29 8 Strengthening Caeser Key weakness is fixed by monoalphabetic substitution Strengths 403,291,461,126,605,635,584,000,000 keys Fast Weaknesses How many keys are easy to remember? Frequency analysis We saw the frequencies of individual letters, but it is also possible---and reasonable---to look at pairs of letters, and triples, etc. More on this in three weeks. Strengthening Caeser : 04/03/29 9 Strengthening Caeser Fixing Frequency analysis Many ways to make frequency analysis harder: send “e” to 3 letters (do you really need z and x?) spell poorly (do you really need all those silent letters?) send short messages use several different keys in one message Vigenère’s Cryptosystem : 04/03/29 10 Vigenère’s Cryptosystem Let’s encrypt the plaintext “prince is my favorite musician” with the keyword “GUITAR”. Step 1: strip formatting: “prince ismyfa vorite musici an” using blocks the same length as our keyword. Step 2: encrypt the first letter of each block with the Caeser-cipher that sends “a” to “G”, the second with that C-c that sends “a” to “U”, the third with that C-c that sends “a” to “I”, the fourth by sending “a” to “T”, fifth by sending “a” to “A”, the sixth by sending “a” to “R”. VLQGCV OMURFR BIZBTV SOABCZ GH Step 3: reformat into a (possibly) different block length. VLQG CVOM URFR BIZB TVSO ABCZ GH Vigenère’s Cryptosystem : 04/03/29 11 Vigenère’s Cryptosystem Strengths Infinite number of keywords Scrambles frequencies Easy to remember key Considered unbreakable in Black chambers for 200 years Weaknesses Can perform frequency analysis if we know-or guess-the length of the keyword Vigenère’s Cryptosystem : 04/03/29 12 Vigenère’s Cryptosystem History Idea of entertwining two keys came from Leon Battista Alberti around 1465 in Florence Developed by Johannes Trithemius Giovanni Porta Blaise de Vigenère The Alpha and the Omega of Vigenère’s cryptosystem : 04/03/29 13 The Alpha and the Omega of Vigenère’s cryptosystem Vigenère’s Cryptosystem : 04/03/29 14 Vigenère’s Cryptosystem History Idea of entertwining two keys came from Leon Battista Alberti around 1465 in Florence Developed by Johannes Trithemius Giovanni Porta Blaise de Vigenère Broken by Charles Babbage Publicly broken by Friedrich Kasiski The Vision of Sin : 04/03/29 15 The Vision of Sin Sit thee down, and have no shame, Cheek by jowl, and knee by knee: What car I for any name? What for order or degree? Let me screw thee up a peg: Let me loose thy tongue with wine: Callest thou that thing a leg? Which is thinnest? Thine or mine? Thou shalt not be saved by works: Thou has been a sinner too: Ruined trunks on withered forks, Empty scarecrows, I and you! Fill the cup, and fill the can: Have a rouse before the morn: Every moment dies a man, Every moment one is born. Alfred Tennyson Image taken from http://charon.sfsu.edu/TENNYSON/tennyson.html Babbage to Tennyson : 04/03/29 16 Babbage to Tennyson [suggested correction to “otherwise beautiful” poem] It must be manifest that if this were true, the population of the world would be at a standstill . . . I would suggest that in the next edition of your poem you have it read – “Every moment dies a man, Every moment 1 1/16 is born.” The actual figure is so long I cannot get it onto a line, but I believe the figure 1 1/16 will be sufficiently accurate for poetry. Transpositions : 04/03/29 17 Transpositions Part of an actual telegram from Union Army General Halleck to General Buell (quoted from Battle Cry of Freedom: The Civil War Era) YOU MARCHED THE IS THE ELSEWHERE MOVE OF SURPRISING TWO TIMES HALLECK AS SLOWLY ARMY IN HAS DISTANCE HAVE FOUR LAST MOST IMMOBILITY YOU HERE TOO YOUR BRAGG MONTHS THE From Lincoln : 04/03/29 18 From Lincoln 1863 WOULD RELIEVED MEADE SINCE HAVE THE WITHOUT ME WAS WHO THE SATURDAY HEVY A WAR FIGHTING CORPS KNOW PLEASE THE TO OF AND IMPRESSION TO CAMERON 15 I BE THAT ALL GETTYSBURG GET RIVER TELL WHO COMMANDER IN ON LINCOLN SIGNED OF FOR ONE YOU FIGHT OVER ONLY BATTLE SMITH THE MUCH SIMON WASHINGTON FOR GIVE OF COUCH THE STRIVEN ENEMY ANOTHER IF THE WAS COUNCIL NIGHT Image from http://www.picturehistory.com/ Rectangular Transposition : 04/03/29 19 Rectangular Transposition Let’s encrypt “Out of life’s school of war: What does not destroy me, makes me stronger.” with keyword Nietzsche The lexicographically first letter in our keyword is c, followed by e, e, h, i, n, s, t, z: 6 5 2 8 9 7 1 4 3 Rectangular Transposition : 04/03/29 20 Rectangular Transposition Step 2: Write the plaintext under the permutation rowwise Rectangular Transposition : 04/03/29 21 Rectangular Transposition Step 3: Write down the columns according to the numbers at the top: ILTEAOU TCRNYEQ EFOTEGR FODSKNV USASOMR OSWERSE LOADMRZ OHWOMSJ FOHTETX Rectangular Transposition : 04/03/29 22 Rectangular Transposition Step 4: Break into grams of a different length: ILTEAOU TCRNYEQ EFOTEGR FODSKNV USASOMR OSWERSE LOADMRZ OHWOMSJ FOHTETX becomes ILTEA OUTCR NYEQE FOTEG RFODS KNVUS ASOMR OSWER SELOA DMRZO HWOMS JFOHT ETX Grades : 04/03/29 23 Grades 6 out of 7 quizzes (60%) Computer Homework (20%) Final Exam (or project) (20%) Summary : 04/03/29 24 Summary Caeser Sucks Monoalphabetic substitution is better Vigenère is good Transposition is a nice idea, and deserves to be looked at more The End You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
Anthony Zanontian - Cryptography anthony.zanontian Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 647 Category: Education License: All Rights Reserved Like it (0) Dislike it (0) Added: March 10, 2009 This Presentation is Public Favorites: 1 Presentation Description No description available. Comments Posting comment... By: anand13 (10 month(s) ago) good plz give it Saving..... Post Reply Close Saving..... Edit Comment Close By: muthukumar852 (14 month(s) ago) gppd Saving..... Post Reply Close Saving..... Edit Comment Close By: nagarakhilesh (14 month(s) ago) pls send me... Saving..... Post Reply Close Saving..... Edit Comment Close By: gazalshabab (15 month(s) ago) plz send this ppt on my email id gazal_shabab@yahoo.com Saving..... Post Reply Close Saving..... Edit Comment Close By: kakerot (26 month(s) ago) HEY BUDDY .. THE PRESENTATION IS AWESOME. I NEED IT . IF POSSIBLE PLEASE SEND IT TO ME... MY ID IS:- rayovania@gmail.com... damn good work.. seriously hoping to get ur ppt... thank you Saving..... Post Reply Close Saving..... Edit Comment Close Premium member Presentation Transcript Cryptography : 04/03/29 1 Cryptography Kevin O’Bryant kobryant@ucsd.edu www.math.ucsd.edu/~kobryant Math 187 MWF 4:00 – 4:50 pm www.math.ucsd.edu/~crypto Definitions : 04/03/29 2 Definitions Plaintext The message that Alice wants Bob to read Ciphertext The message that Alice sends Bob Cryptosystem The algorithm that Alice uses to turn plaintext into ciphertext. Key Something Bob and Alice agree on beforehand that customizes the cryptosystem Cryptosystems : 04/03/29 3 Cryptosystems Two basic types: Substitution (replace letters) Transposition (rearrange letters) Caeser Cipher Shift each letter by the same amount Key: how much to shift Monoalphabetic Substitution Replace each letter with some other letter in a one-to-one manner Key: the bottom line of Plaintext: abcdefghijklmnopqrstuvwxyz Ciphertext: QWERTYUIOPASDFGHJKLZXCVBNM Caeser Cipher : 04/03/29 4 Caeser Cipher GZO PN OCZMZAJMZ WMVXZ JPMNZGQZN OJ JPM YPOT, VIY NJ WZVM JPMNZGQZN, OCVO DA OCZ WMDODNC ZHKDMZ VIY DON XJHHJIRZVGOC GVNO AJM V OCJPNVIY TZVMN, HZI RDGG NODGG NVT, 'OCDN RVN OCZDM ADIZNO CJPM.‘ Caeser Cipher Strengths Very Fast Easy to remember Cipher Wheels : 04/03/29 5 Cipher Wheels Caeser Cipher : 04/03/29 6 Caeser Cipher GZO PN OCZMZAJMZ WMVXZ JPMNZGQZN OJ JPM YPOT, VIY NJ WZVM JPMNZGQZN, OCVO DA OCZ WMDODNC ZHKDMZ VIY DON XJHHJIRZVGOC GVNO AJM V OCJPNVIY TZVMN, HZI RDGG NODGG NVT, 'OCDN RVN OCZDM ADIZNO CJPM.‘ Caeser Cipher Strengths Very Fast Easy to remember Weaknesses Formatting gives away the house Small number of keys: 26 (and one is weak) Frequency analysis Strengthening Caeser : 04/03/29 7 Strengthening Caeser Fixing the Formatting Weakness Strip out punctuation, and put letters in blocks of the same length. GZO PN OCZMZAJMZ WMVXZ JPMNZGQZN OJ JPM YPOT, VIY NJ WZVM JPMNZGQZN, OCVO DA OCZ WMDODNC ZHKDMZ VIY DON XJHHJIRZVGOC GVNO AJM V OCJPNVIY TZVMN, HZI RDGG NODGG NVT, 'OCDN RVN OCZDM ADIZNO CJPM.‘ becomes GZOP NOCZ MZAJ MZWM VXZJ PMNZ GQZN OJJP MYPO TVIY NJWZ VMJP MNZG QZNO CVOD AOCZ WMDO DNCZ HKDM ZVIY DONX JHHJ IRZV GOCG VNOA JMVO CJPN VIYT ZVMN HZIR DGGN ODGG NVTO CDNR VNOC ZDMA DIZN OCJP M Strengthening Caeser : 04/03/29 8 Strengthening Caeser Key weakness is fixed by monoalphabetic substitution Strengths 403,291,461,126,605,635,584,000,000 keys Fast Weaknesses How many keys are easy to remember? Frequency analysis We saw the frequencies of individual letters, but it is also possible---and reasonable---to look at pairs of letters, and triples, etc. More on this in three weeks. Strengthening Caeser : 04/03/29 9 Strengthening Caeser Fixing Frequency analysis Many ways to make frequency analysis harder: send “e” to 3 letters (do you really need z and x?) spell poorly (do you really need all those silent letters?) send short messages use several different keys in one message Vigenère’s Cryptosystem : 04/03/29 10 Vigenère’s Cryptosystem Let’s encrypt the plaintext “prince is my favorite musician” with the keyword “GUITAR”. Step 1: strip formatting: “prince ismyfa vorite musici an” using blocks the same length as our keyword. Step 2: encrypt the first letter of each block with the Caeser-cipher that sends “a” to “G”, the second with that C-c that sends “a” to “U”, the third with that C-c that sends “a” to “I”, the fourth by sending “a” to “T”, fifth by sending “a” to “A”, the sixth by sending “a” to “R”. VLQGCV OMURFR BIZBTV SOABCZ GH Step 3: reformat into a (possibly) different block length. VLQG CVOM URFR BIZB TVSO ABCZ GH Vigenère’s Cryptosystem : 04/03/29 11 Vigenère’s Cryptosystem Strengths Infinite number of keywords Scrambles frequencies Easy to remember key Considered unbreakable in Black chambers for 200 years Weaknesses Can perform frequency analysis if we know-or guess-the length of the keyword Vigenère’s Cryptosystem : 04/03/29 12 Vigenère’s Cryptosystem History Idea of entertwining two keys came from Leon Battista Alberti around 1465 in Florence Developed by Johannes Trithemius Giovanni Porta Blaise de Vigenère The Alpha and the Omega of Vigenère’s cryptosystem : 04/03/29 13 The Alpha and the Omega of Vigenère’s cryptosystem Vigenère’s Cryptosystem : 04/03/29 14 Vigenère’s Cryptosystem History Idea of entertwining two keys came from Leon Battista Alberti around 1465 in Florence Developed by Johannes Trithemius Giovanni Porta Blaise de Vigenère Broken by Charles Babbage Publicly broken by Friedrich Kasiski The Vision of Sin : 04/03/29 15 The Vision of Sin Sit thee down, and have no shame, Cheek by jowl, and knee by knee: What car I for any name? What for order or degree? Let me screw thee up a peg: Let me loose thy tongue with wine: Callest thou that thing a leg? Which is thinnest? Thine or mine? Thou shalt not be saved by works: Thou has been a sinner too: Ruined trunks on withered forks, Empty scarecrows, I and you! Fill the cup, and fill the can: Have a rouse before the morn: Every moment dies a man, Every moment one is born. Alfred Tennyson Image taken from http://charon.sfsu.edu/TENNYSON/tennyson.html Babbage to Tennyson : 04/03/29 16 Babbage to Tennyson [suggested correction to “otherwise beautiful” poem] It must be manifest that if this were true, the population of the world would be at a standstill . . . I would suggest that in the next edition of your poem you have it read – “Every moment dies a man, Every moment 1 1/16 is born.” The actual figure is so long I cannot get it onto a line, but I believe the figure 1 1/16 will be sufficiently accurate for poetry. Transpositions : 04/03/29 17 Transpositions Part of an actual telegram from Union Army General Halleck to General Buell (quoted from Battle Cry of Freedom: The Civil War Era) YOU MARCHED THE IS THE ELSEWHERE MOVE OF SURPRISING TWO TIMES HALLECK AS SLOWLY ARMY IN HAS DISTANCE HAVE FOUR LAST MOST IMMOBILITY YOU HERE TOO YOUR BRAGG MONTHS THE From Lincoln : 04/03/29 18 From Lincoln 1863 WOULD RELIEVED MEADE SINCE HAVE THE WITHOUT ME WAS WHO THE SATURDAY HEVY A WAR FIGHTING CORPS KNOW PLEASE THE TO OF AND IMPRESSION TO CAMERON 15 I BE THAT ALL GETTYSBURG GET RIVER TELL WHO COMMANDER IN ON LINCOLN SIGNED OF FOR ONE YOU FIGHT OVER ONLY BATTLE SMITH THE MUCH SIMON WASHINGTON FOR GIVE OF COUCH THE STRIVEN ENEMY ANOTHER IF THE WAS COUNCIL NIGHT Image from http://www.picturehistory.com/ Rectangular Transposition : 04/03/29 19 Rectangular Transposition Let’s encrypt “Out of life’s school of war: What does not destroy me, makes me stronger.” with keyword Nietzsche The lexicographically first letter in our keyword is c, followed by e, e, h, i, n, s, t, z: 6 5 2 8 9 7 1 4 3 Rectangular Transposition : 04/03/29 20 Rectangular Transposition Step 2: Write the plaintext under the permutation rowwise Rectangular Transposition : 04/03/29 21 Rectangular Transposition Step 3: Write down the columns according to the numbers at the top: ILTEAOU TCRNYEQ EFOTEGR FODSKNV USASOMR OSWERSE LOADMRZ OHWOMSJ FOHTETX Rectangular Transposition : 04/03/29 22 Rectangular Transposition Step 4: Break into grams of a different length: ILTEAOU TCRNYEQ EFOTEGR FODSKNV USASOMR OSWERSE LOADMRZ OHWOMSJ FOHTETX becomes ILTEA OUTCR NYEQE FOTEG RFODS KNVUS ASOMR OSWER SELOA DMRZO HWOMS JFOHT ETX Grades : 04/03/29 23 Grades 6 out of 7 quizzes (60%) Computer Homework (20%) Final Exam (or project) (20%) Summary : 04/03/29 24 Summary Caeser Sucks Monoalphabetic substitution is better Vigenère is good Transposition is a nice idea, and deserves to be looked at more The End