צופן קיסר בג'אווה

1. סקירה כללית

במדריך זה נלך לחקור את צופן קיסר, שיטת הצפנה המעבירה אותיות של הודעה כדי לייצר עוד אחת, פחות קריאה.

קודם כל נעבור את שיטת הצפנה ונראה כיצד ליישם אותה בג'אווה.

לאחר מכן נראה כיצד לפענח הודעה מוצפנת, בתנאי שנדע לקיזוז המשמש להצפנתה.

ולבסוף, נלמד כיצד לשבור צופן כזה ובכך לשלוף את ההודעה המקורית מהמקודן המוצפן מבלי לדעת את הקיזוז בשימוש.

2. צופן קיסר

2.1. הֶסבֵּר

ראשית, בואו נגדיר מהו צופן. צופן הוא שיטה להצפנת הודעה, מתוך כוונה להפוך אותה לקריאה פחות. באשר לצופן הקיסר, זהו צופן תחליפי שהופך מסר על ידי העברת אותיותיו בקיזוז נתון.

נניח שאנחנו רוצים לשנות את האלף-בית ב -3, ואז באות א יהפוך לאותיות ד, ב ל ה, ג ל F, וכולי.

הנה ההתאמה המלאה בין אותיות מקוריות לאותיות מקוריות לקיזוז של 3:

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 D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

כמו שאנו יכולים לראות, ברגע שהטרנספורמציה חורגת מהאות ז, אנו חוזרים לתחילת האלף-בית, כך איקס, י ו ז הופכים ל א, ב ו ג, בהתאמה.

לכן, אם אנו בוחרים קיזוז גדול או שווה ל -26, אנו מקפידים, לפחות פעם אחת, על כל האלף-בית. בואו נדמיין שאנחנו משנים הודעה ב -28, זה באמת אומר שאנחנו משנים אותה ב -2. אכן, לאחר הסטה ב 26, כל האותיות תואמות את עצמן.

באמת, אנו יכולים להפוך כל קיזוז לקיזוז פשוט יותר על ידי ביצוע פעולת מודול 26 בו:

קיזוז = קיזוז% 26

2.2. אלגוריתם בג'אווה

עכשיו, בואו נראה כיצד ליישם את צופן הקיסר בג'אווה.

ראשית, בואו ניצור כיתה צופן קיסר שיחזיק א צוֹפֶן() שיטת לקיחת הודעה וקיזוז כפרמטרים:

מחלקה ציבורית CaesarCipher {צופן מחרוזת (הודעת מחרוזת, אופסט)) {}}

שיטה זו תצפין את ההודעה באמצעות צופן קיסר.

נניח כאן שקיזוזים חיוביים והודעות מכילות רק אותיות קטנות וריווחים. ואז, מה שאנחנו רוצים זה להזיז את כל התווים האלפביתיים בקיזוז הנתון:

תוצאת StringBuilder = StringBuilder חדש (); עבור (תו char: message.toCharArray ()) {if (character! = '') {int originalAlphabetPosition = character - 'a'; int newAlphabetPosition = (originalAlphabetPosition + קיזוז)% 26; char newCharacter = (char) ('a' + newAlphabetPosition); result.append (newCharacter); } אחר {result.append (תו); }} להחזיר תוצאה;

כמו שאנו יכולים לראות, אנו מסתמכים על קודי ASCII של אותיות האלף-בית כדי להשיג את מטרתנו.

ראשית, אנו מחשבים את מיקום האות הנוכחית באלף בית, ולשם כך אנו לוקחים את קוד ה- ASCII שלו ומחסירים את קוד האות ASCII. א מזה. לאחר מכן אנו מיישמים את הקיזוז למיקום זה, תוך שימוש בזהירות במודולו כדי להישאר בטווח האלפבית. ולבסוף, אנו מאחזרים את התו החדש על ידי הוספת המיקום החדש לקוד האות ASCII א.

עכשיו, בואו ננסה את היישום הזה בהודעה "הוא אמר לי שלעולם לא אוכל ללמד לאמה לנהוג" בקיזוז של 3:

צופן קיסר = צופן קיסר חדש (); מחרוזת cipheredMessage = cipher.cipher ("הוא אמר לי שלעולם לא אוכל ללמד לאמה לנהוג", 3); assertThat (cipheredMessage) .isEqualTo ("kh wrog ph l frxog qhyhu whdfk d oodpd wr gulyh");

כפי שאנו רואים, ההודעה המוצפנת מכבדת את ההתאמה שהוגדרה קודם לקיזוז של 3.

כעת, לדוגמא מסוימת זו יש את הספציפיות שלא לחרוג מהאות z במהלך השינוי, ולכן לא צריך לחזור לתחילת האלף-בית. לפיכך, בואו ננסה שוב עם קיזוז של 10 כך שכמה אותיות ימופו לאותיות בתחילת האלף-בית, כמו t אשר ימופה ד:

מחרוזת cipheredMessage = cipher.cipher ("הוא אמר לי שלעולם לא אוכל ללמד לאמה לנהוג", 10); assertThat (cipheredMessage) .isEqualTo ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo");

זה עובד כמצופה, בזכות פעולת המודולו. פעולה זו מטפלת גם בקיזוזים גדולים יותר. נניח שאנחנו רוצים להשתמש ב- 36 כקיזוז, שווה ערך ל- 10, פעולת המודול מבטיחה שהטרנספורמציה תיתן את אותה התוצאה.

3. לפענח

3.1. הֶסבֵּר

עכשיו, בואו נראה איך לפענח הודעה כזו כשאנחנו יודעים שהקיזוז משמש להצפנה.

למעשה, פענוח הודעה המוצפנת בצופן קיסר ניתן לראות כמצפין אותה עם קיזוז שלילי, או גם צופן אותה עם קיזוז משלים.

אז נניח שיש לנו הודעה מוצפנת בקיזוז 3. ואז נוכל להצפין אותה בקיזוז -3 או להצפין בקיזוז 23. כך או כך, אנו מאחזרים את ההודעה המקורית.

למרבה הצער, האלגוריתם שלנו לא מטפל בקיזוז שלילי מחוץ לקופסה. נתקל בבעיות בהמרת אותיות החוזרות לסוף האלף בית (למשל בהפיכת האות א לתוך המכתב z עם קיזוז של -1). אבל, אנו יכולים לחשב את הקיזוז המשלים, שהוא חיובי, ואז להשתמש באלגוריתם שלנו.

אז איך להשיג קיזוז משלים זה? הדרך הנאיבית לעשות זאת תהיה להפחית את הקיזוז המקורי מ- 26. כמובן, זה יעבוד לקיזוז בין 0 ל -26, אך אחרת ייתן תוצאות שליליות.

זה המקום נשתמש שוב במפעיל המודולו, ישירות בקיזוז המקורי, לפני שנבצע את החיסור. בדרך זו אנו מבטיחים תמיד להחזיר קיזוז חיובי.

3.2. אלגוריתם בג'אווה

בואו וניישם את זה עכשיו ב- Java. ראשית, נוסיף א לְפַעֲנֵחַ() שיטה לשיעור שלנו:

פענוח מחרוזת (הודעת מחרוזת, אופסט אינט)

ואז, בוא נקרא צוֹפֶן() שיטה עם הקיזוז המשלים המחושב שלנו:

צופן החזרה (הודעה, 26 - (קיזוז% 26));

זהו זה, אלגוריתם הפענוח שלנו מוגדר. בואו ננסה את זה בדוגמה עם קיזוז 36:

String decipheredSentence = cipher.decipher ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo", 36); assertThat (decipheredSentence) .isEqualTo ("הוא אמר לי שלעולם לא אוכל ללמד לאמה לנהוג");

כפי שאנו רואים, אנו מאחזרים את המסר המקורי שלנו.

4. שוברים את צופן הרזלים

4.1. הֶסבֵּר

כעת, לאחר שסיקרנו קידוד ופענוח הודעות באמצעות צופן קיסר, נוכל לצלול כיצד לשבור אותו. כלומר, לפענח הודעה מוצפנת מבלי לדעת בהתחלה את הקיזוז המשומש.

לשם כך נשתמש בהסתברויות למציאת אותיות באנגלית בטקסט. הרעיון יהיה לפענח את ההודעה באמצעות קיזוז 0 עד 25 ולבדוק איזו משמרת מציגה פיזור אותיות דומה לזה של טקסטים באנגלית.

על מנת לקבוע את הדמיון של שתי התפלגויות, נשתמש בנתון הצ'י בריבוע.

הסטטיסטיקה בריבוע הצ'י תספק מספר שיאמר לנו אם שתי התפלגויות דומות או לא. ככל שהמספר קטן יותר, כך הם דומים יותר.

אז נחשב את ריבוע הצ'י עבור כל קיזוז ואז נחזיר את ריבוע הצ'י הקטן ביותר. זה אמור לתת לנו את הקיזוז המשמש לפענוח המסר.

עם זאת, עלינו לזכור זאת טכניקה זו אינה חסינת קליעים ובמידה וההודעה תהיה קצרה מדי או שמשתמשים במילים לצערנו אינם מייצגים טקסט רגיל באנגלית, היא עשויה להחזיר קיזוז שגוי.

4.2. הגדר את חלוקת אותיות הבסיס

בואו נראה כעת כיצד ליישם את האלגוריתם השובר בג'אווה.

קודם כל, בואו ניצור a breakCipher () השיטה שלנו צופן קיסר class, שיחזיר את הקיזוז המשמש להצפנת הודעה:

int breakCipher (הודעת מחרוזת) {}

לאחר מכן, נגדיר מערך המכיל את ההסתברויות למציאת אות מסוימת בטקסט באנגלית:

כפול [] englishLettersProbabilities = {0.073, 0.009, 0.030, 0.044, 0.130, 0.028, 0.016, 0.035, 0.074, 0.002, 0.003, 0.035, 0.025, 0.078, 0.074, 0.027, 0.003, 0.077, 0.063, 0.093, 0.027, 0.013, 0.016, 0.005, 0.019, 0.001};

ממערך זה נוכל לחשב את התדרים הצפויים של האותיות בהודעה נתונה, על ידי הכפלת ההסתברויות לאורך ההודעה:

כפול [] expectLettersFrequences = Arrays.stream (englishLettersProbabilities) .map (probability -> probability * message.getLength ()) .toArray ();

לדוגמא, בהודעה באורך 100, עלינו לצפות לאות א להופיע 7.3 פעמים, והמכתב ה להופיע 13 פעמים.

4.3. חשב את ריבועי הצ'י

כעת נחשב את ריבועי הצ'י של חלוקת אותיות הודעות מפוענחות והפצת אותיות אנגליות רגילות.

כדי להשיג זאת, נצטרך לייבא את ספריית Apache Commons Math3 המכילה מחלקת כלי עזר לחישוב ריבועי צ'י:

 org.apache.commons commons-math3 3.6.1 

מה שאנחנו צריכים לעשות עכשיו זה לעשות צור מערך שיכיל את ריבועי הצ'י המחושבים עבור כל קיזוז בין 0 ל -25.

לפיכך, נפענח את ההודעה המוצפנת באמצעות כל קיזוז, ונמנה את האותיות בהודעה זו.

לבסוף נשתמש ב- ChiSquareTest # chiSquare שיטה לחישוב ריבוע הצ'י בין התפלגות האותיות הצפויה לתצפית:

כפול [] chiSquares = כפול חדש [26]; עבור (int offset = 0; offset <chiSquares.length; offset ++) {String decipheredMessage = decipher (message, offset); [] lettersFrequences ארוך = נצפה LettersFrequences (decipheredMessage); כפול chiSquare = ChiSquareTest חדש (). chiSquare (expectLettersFrequences, lettersFrequences); chiSquares [קיזוז] = chiSquare; } להחזיר chiSquares;

ה seenLettersFrequences () השיטה פשוט מממשת ספירת אותיות א ל z בהודעה שהועברה:

long [] observerLettersFrequences (הודעת מחרוזת) {return IntStream.rangeClosed ('a', 'z') .mapToLong (letter -> countLetter ((char) letter, message)) .toArray (); } countLetter ארוך (אות אות, הודעת מחרוזת) {return message.chars () .filter (character -> character == letter) .count (); }

4.4. מצא את הקיזוז האפשרי ביותר

לאחר חישוב כל ריבועי הצ'י, נוכל להחזיר את הקיזוז התואם לריבוע הצ'י הקטן ביותר:

int probableOffset = 0; עבור (int offset = 0; offset <chiSquares.length; offset ++) {System.out.println (String.format ("כיכר צ'י לקיזוז% d:% .2f", offset, chiSquares [offset])); אם (chiSquares [offset] <chiSquares [probableOffset]) {probableOffset = offset; }} להחזיר probableOffset;

למרות שאין צורך להזין את הלולאה עם קיזוז 0 מכיוון שאנו רואים את זה כמינימום לפני התחלת הלולאה, אנו עושים זאת כדי להדפיס את ערך הריבוע הצ'י שלה.

בואו ננסה את האלגוריתם הזה בהודעה המוצפנת באמצעות קיזוז 10:

int offset = algorithm.breakCipher ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo"); assertThat (קיזוז). isEqualTo (10); assertThat (אלגוריתם. לפענח ("ro dyvn wo s myevn xofob dokmr k vvkwk dy nbsfo", קיזוז)) .isEqualTo ("הוא אמר לי שלעולם לא אוכל ללמד ללמה לנהוג");

כפי שאנו רואים, השיטה מאחזרת את הקיזוז הנכון, אשר באמצעותו ניתן לפענח את ההודעה ולאחזר את ההודעה המקורית.

להלן ריבועי הצ'י השונים המחושבים עבור הפסקה מסוימת זו:

כיכר צ'י לקיזוז 0: 210.69 כיכר צ'י לקיזוז 1: 327.65 כיכר צ'י לקיזוז 2: 255.22 כיכר צ'י לקיזוז 3: 187.12 כיכר צ'י לקיזוז 4: 734.16 כיכר צ'י לקיזוז 5: 673.68 צ'י ריבוע לקיזוז 6: 223.35 צ'י-ריבוע לקיזוז 7: 111.13 צ'י-ריבוע לקיזוז 8: 270.11 צ'י-ריבוע לקיזוז 9: 153.26 כיכר צ'י לקיזוז 10: 23.74 צ'י-ריבוע לקיזוז 11: 643.14 צ'י-ריבוע עבור קיזוז 12: 328.83 כיכר צ'י לקיזוז 13: 434.19 כיכר צ'י לקיזוז 14: 384.80 כיכר צ'י לקיזוז 15: 1206.47 כיכר צ'י לקיזוז 16: 138.08 כיכר צ'י לקיזוז 17: 262.66 כיכר צ'י לקיזוז 18 : 253.28 כיכר צ'י לקיזוז 19: 280.83 כיכר צ'י לקיזוז 20: 365.77 כיכר צ'י לקיזוז 21: 107.08 כיכר צ'י לקיזוז 22: 548.81 כיכר צ'י לקיזוז 23: 255.12 צ'י-ריבוע לקיזוז 24: 458.72 כיכר צ'י לקיזוז 25: 325.45

כפי שאנו רואים, זה עבור קיזוז 10 הוא ברור יותר מהאחרים.

5. מסקנה

במאמר זה סקרנו את צופן קיסר. למדנו כיצד לפענח ולפענח הודעה על ידי העברת אותיותיה בקיזוז נתון. למדנו גם איך לשבור את הצופן. וראינו את כל יישומי Java המאפשרים לנו לעשות זאת.

הקוד של מאמר זה ניתן למצוא באתר GitHub.