קריפטוגרפיה

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

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

השם "קריפטוגרפיה" מקורו במילה היוונית "קריפטו" (κρυπτός) שמשמעותה נסתר או אמנות ההסתרה, ו"גרפיה" (γράφω) שמשמעותה רישום. בתרגום חופשי נעשה שימוש בשם באופן חליפי למונח קריפטולוגיה שפירושו תורת ההסתרה (Crypto-logia, κρυπτός-λογία), אם כי משמעותו רחבה יותר מתחום ההצפנה בלבד.

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

מונחים כלליים

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

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

המונח צופן (Cipher) מתייחס לאלגוריתם הצפנה, כאשר קלט האלגוריתם נקרא "טקסט קריא" או "טקסט גלוי" (באנגלית: Plaintext). ואילו פלט האלגוריתם נקרא "טקסט מוצפן" או "כתב סתר" (באנגלית: Ciphertext). בשפה העברית משמשת המילה צופן גם כשם עצם לכתב סתר או קוד.

רקע היסטורי

קריפטוגרפיה בעת העתיקה

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

שורשיה של הקריפטוגרפיה נעוצים בשחר ההיסטוריה. בראשית דרכה עסקה בעיקר בשיטות הצפנה לקסיקוגרפיות פרימיטיביות למדי ובסטגנוגרפיה. קיימים ממצאים המעידים כי המצרים הקדמונים השתמשו בהצפנה בכתב חרטומים, לערך 3000 שנה לפנה"ס‏‏. בתנ"ך ובמקורות יהודיים נוספים קיימות עדויות נוספות להצפנה. לדוגמה, בספר ירמיהו (נכתב בשלהי תקופת בית ראשון, לפני שנת 586 לפנה"ס), נעשה שימוש בצופן אתב"ש: "ומלך ששך ישתה אחריהם" (ירמיהו כה כו), "..אל ישבי לב קמי רוח משחית" (ירמיהו נא א). ‎ "ששך" היא "בבל" בצופן אתב"ש, ו"לב קמי" היא "כשדים".

השימוש בהצפנה התרחב בתקופת יוון העתיקה. צופן הזזה פשוט היה בשימוש צבא ספרטה‏, בצופן זה, כל אות משנה את מיקומה לפי חוק מסוים. צפנים אלו מומשו, למשל, בעזרת גליל הצפנה (ראו תמונה). יוליוס קיסר (102 עד 40 לפנה"ס) נהג להשתמש בשיטת הצפנה מתקדמת יותר, צופן החלפה, בו כל אות נשארת במקומה אך מוחלפת באות שונה לפי חוקיות מסוימת. הצופן בו השתמש יוליוס קיסר נודע לימים כצופן קיסר. (ראו בהמשך הסבר על צפני הזזה והחלפה.) בתקופה זו נעשה שימוש בשיטות סטגנוגרפיות, כגון קעקוע המסר על ראשו המגולח של חייל ושליחתו ליעד לאחר שצמחו שערותיו, או כתיבת המסר על לוחות עץ וציפויים בשעווה לאחר מכן.

קריפטוגרפיה בעת החדשה

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

בימי הביניים ובעת החדשה נעשה שימוש רב בהצפנה מסוגים שונים. צופן הזזה ב"שיטת הרשת" שימש את האפיפיור.‏‏ צפני הזזה (אנגרמות) שימשו מדענים כגון גלילאו גלילי (המאה ה-16) להחבאת סודות או על מנת להוכיח זכות ראשונים על גילויים מדעיים. מרי, מלכת הסקוטים (המאה ה-16) עשתה שימוש בצופן החלפה על מנת להתכתב עם קבוצת אצילים קתוליים שרצו להדיח את המלכה אליזבת הראשונה מהכתר. שבירת צופן זה על ידי שרות הריגול של המלכה אליזבת עלתה למלכה מרי בחייה.‏‏

בתקופה זו החל גם העיסוק בנסיונות שבירה של צפנים פשוטים. במהלך המאה ה-9 פותחה על ידי איש האשכולות העיראקי אל-קינדי (801-873) שיטת פיצוח צפנים המבוססת על ניתוח תדירויות. ככל הנראה, ניתוח התדירויות החל בעקבות בחינה של כתבי הקוראן ונסיון לנתח אותם. שיטה זו הייתה שימושית לפיצוח צפנים עד שלהי המאה ה-20 ופיתוח ההצפנה המודרנית. אל-קינדי פרט את ממצאיו בספר שהכיל, בין היתר, מספר שיטות לפיצוח צפנים (חלקן עבור צפנים פוליאלפביתיים), סיווג צפנים שונים, וניתוח תדירויות אותיות בשפה הערבית.‏‏

הסופר והמתמטיקאי המצרי אל-קאלקשנדי (1355 - 1418) כתב אנציקלופדיה שהכילה פרק בנושא קריפטוגרפיה. כתבים אלו הכילו צפני הזזה וצפני החלפה פשוטים, וכן צפני החלפה בהם כל אות מוחלפת באות אחרת מתוך מבחר של מספר אותיות שונות. כמו כן מתוארים שיטות קריפטאנליטיות מבוססות ניתוח תדירויות של אותיות, וצרופי אותיות שלא יופיעו זו אחר זו בטקסט. ייתכן שכתבים אלו מקורם בעבודתו של טאג' א-דין עלי (1312 - 1361).

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

קריפטוגרפיה עד אמצע המאה ה-20

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

בשנת 1854 המציא המדען הבריטי צ'ארלס ויטסטון שיטת הצפנה חדשה אשר נודעה לימים כצופן פלייפייר. בשיטה זו התבצעה ההצפנה לראשונה על קבוצת אותיות ולא על כל אות בנפרד. בצופן פלייפייר ההצפנה מבוצעת על זוגות של אותיות (דיגרפים). עובדה זו מקשה את שבירת הצופן בטכניקה של ניתוח תדירויות, כיוון שכעת יש לנתח תדירויות של כ-600 דיגרפים (צירופי אותיות) שונים, לעומת כמות של כ-26 אותיות. הרחבה של רעיון זה הובילה למושג צופן בלוקים הנפוץ בקריפטולוגיה המודרנית.

עם התפתחות הטכנולוגיה גבר גם השימוש בהצפנה ובפרט הצפנה ממוכנת (ראו מכונות מבוססות רוטור בהמשך). הקריפטוגרפיה הפכה כלי בסיסי להצפנת ידיעות צבאיות טרם שליחתן בטלגרף או ברדיו. במקביל גורמי מודיעין רבים עסקו בניסיונות פיצוח צפנים של צבאות אויב. בשנת 1917 הגה המהנדס גילברט סטנפורד ורנם (1890 - 1960) שיטה ממוכנת לביצוע הצפנה בטלגרף, בה המידע מוצפן תו אחר תו בעת שידורו, בניגוד לביצוע ההצפנה מראש ולאחר מכן שידור הטקסט המוצפן. בשיטה זו המפתח מוכן מראש על גבי סרט מנוקב ומחובר על ידי ממסר חשמלי אל מכונת הטלגרף. שיטת הצפנה זו ידועה בשם צופן ורנם, על שם ממציאה, והיוותה את הבסיס להצפנת פנקס חד-פעמי הבלתי-שבירה.

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

• מברק צימרמן: מברק מוצפן שנשלח במהלך מלחמת העולם הראשונה (16 בינואר 1917) על ידי שר החוץ של גרמניה, ארתור צימרמן, לשגריר גרמניה בארצות הברית, ומטרתו ליזום ברית בין גרמניה למקסיקו כנגד מדינות ההסכמה. המברק הוצפן באמצעות ספר צופן שנפל בידי המודיעין הבריטי. פענוח המברק היה בין הגורמים להצטרפות ארצות הברית ללחימה לצד מדינות ההסכמה.
• פרויקט ונונה (מסמכי וינונה): פרויקט ביון משותף לארצות הברית ואנגליה, לפענוח מסמכים מוצפנים של ברית המועצות שיורטו במהלך מלחמת העולם השנייה, ופוענחו במשך 40 השנים הבאות. מסמכים אלו היוו מקור מידע חשוב עבור הביון של הגוש המערבי במהלך המלחמה הקרה. פיצוח הצופן נבע מטעות שימוש בצד הסובייטי: הצופן בו נעשה שימוש היה מסוג פנקס חד-פעמי, בו כל מפתח משמש פעם יחידה בלבד. ככל הנראה, עקב רצון לחסוך בכמות המפתחות, או עקב הזמן הארוך הנדרש לייצור מפתחות, נעשה שימוש חוזר בחלק מהפנקס החד-פעמי, דבר שהוביל לפענוח חלקי של המסמכים. כ-3,000 מסמכים שיורטו בין השנים 1942 - 1945 פוענחו באופן חלקי או מלא על ידי כוחות הברית, והחל מ-1948 כלל התשדורות שיורטו הפכו בלתי פציחות.‏‏
• שפת הנאוואחו: השפה המדוברת על ידי אינדיאנים בני שבט הנאוואחו. ניתן לראות בה צופן פשוט הידוע רק לדוברי השפה וזאת מכמה סיבות:

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

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

• אניגמה: מכונת הצפנה מבוססת רוטור, ששימשה את גרמניה במהלך מלחמת העולם השנייה. בעלות הברית הצליחו לפצח את ההצפנה, ובמשך רוב המלחמה פענחו מספר גדול של הודעות מוצפנות. על מנת שלא לחשוף את העובדה שהמערכת נפרצה על ידי בעלות הברית, נעשה שימוש זהיר ביותר במודיעין שהופק מיירוט מסרים שהוצפנו באניגמה. כמות המידע שהופק מהודעות אלו ואיכותו הובילו את צ'רצ'יל לומר "הודות לאולטרה (המודיעין שהופק מהאניגמה) ניצחנו במלחמה".‏‏

קריפטוגרפיה מודרנית

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

תקן ההצפנה הראשון, DES, שהתקבל ב-1975, פיתוח של צוות מתמטיקאים מיבמ בשיתוף פעולה עם NSA, היה נקודת ציון חשובה שהגבירה את ההתעניינות הציבורית בתחום. אולם פריצת הדרך אולי החשובה ביותר, אירעה באותה שנה, המצאת ענף חשוב בתורת ההצפנה הקרוי מפתח-פומבי, על ידי ויטפילד דיפי ומרטין הלמן.

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

הצפנה קלאסית

סוגי הצפנה קלאסית

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

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

צופן החלפה הוא שם כללי לצופן בו כל אות מוחלפת על ידי אות אחרת, לפי חוקיות ידועה (המפתח). דוגמה ידועה לצופן החלפה היא צופן קיסר בו השתמש יוליוס קיסר. בצופן זה כל אות מוחלפת באות הבאה אחריה באלפבית בהיסט מסוים וקבוע (באופן מעגלי). לדוגמה, אם ההיסט הוא 3 אותיות (גודל ההיסט בו השתמש יוליוס קיסר), המילה "קיסר" תוחלף במילה "תמצא". בצופן זה, גודל ההיסט הוא המפתח לפענוח המסר. צופן טרנספוזיציה קל לזיהוי ולשבירה כיוון שהוא משמר את תדירות האותיות שבמסר המקורי, וקל לפצחו מכיוון שמספר ההיסטים האפשריים מוגבל מאוד. במובן הכללי יותר, החלפת האותיות בצופן החלפה מתבצעת לפי מפתח המגדיר את ההמרה בין כל אות (או קבוצת אותיות) בטקסט הגלוי, לאות (או קבוצת אותיות) מוצפנת. צופן ויז'נר וצופן ורנם הם דוגמאות נפוצות של צפני החלפה. פעמים רבות המפתח בצופן החלפה הוא ספר צופן, המכיל כמות גדולה של מפתחות לשימוש, למשל דף מפתח ייעודי עבור כל יום בו עושים שימוש בצופן.

הצפנה קלאסית במאה ה-20: מכונות הצפנה מבוססות רוטור

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

גליל ג'פרסון, שרטוט מכונת הצפנה פרימיטיבית המיישמת צופן החלפה רב-אלפביתי. הומצאה על ידי תומאס ג'פרסון בסוף המאה ה-18

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

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

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

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

ניתוח סטטיסטי של צפנים קלאסיים

ערך מורחב – ניתוח תדירויות (קריפטוגרפיה)

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

קיימות מספר שיטות לפענוח צופן רב-אלפביתי עם מפתח קצר, בהן שיטת קסיסקי או מבחן קסיסקי, בה מנסים לאתר את גודל המפתח מתוך מקטעים החוזרים על עצמם בטקסט המוצפן. משנמצא אורך המפתח, מחלקים את הטקסט המוצפן לגושים באורך המפתח ומפעילים ניתוח סטטיסטי על כל גוש בנפרד בהתבסס על שכיחות האותיות. וכן שיטת מדד צירופי מקרים של ויליאם פרידמן שפענח את צופן PURPLE היפני, בה המתקיף מנסה לחשוף את מחזוריות הצופן (אורך המפתח) על ידי מדידת שכיחות יחסית של מקבצי אותיות בטקסט המוצפן בהתבסס על טבלת שכיחויות שהוכנה מראש, שיטה זו טובה כנגד צופן רב-אלפביתי, כגון ספר-צופן (Running key) וכן צופן ויז'נר.

הצפנה מודרנית

תהליך התקשרות מאובטחת כולל שני שלבים בסיסיים:

• הצפנה: שנעשית על ידי השולח ובמסגרתה המסר הגלוי מועבר למצב מוצפן.
• פענוח: שנעשה על ידי המקבל ובמסגרתו המסר המוצפן חוזר להיות גלוי.

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

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

הצפנה סימטרית

ערך מורחב – צופן סימטרי

הצפנה סימטרית היא הוותיקה ביותר ושורשיה החלו עם ההצפנה הקלאסית לפני מאות שנים. בהצפנה סימטרית נעשה שימוש במפתח יחיד להצפנה ולפענוח. על מנת שניתן יהיה להעביר מידע סודי בין הצדדים המתקשרים, שני הצדדים נדרשים להחזיק באותו מפתח הצפנה. יתרונותיה של ההצפנה הסימטרית הם ביעילותה (מפתח הצפנה באורך של 128 סיביות ומעלה באלגוריתם טוב נחשב כמספק) ובכוח המחשוב הנמוך הדרוש ליישומה לעומת הצפנה אסימטרית. דוגמה לאלגוריתם כזה הוא אלגוריתם DES, שהיה לאלגוריתם הסימטרי הראשון שהופץ בקנה מידה גדול ואף הפך לתקן הצפנה רשמי. DES שימש בעיקר בתחום הבנקאות והוא עדיין בשימוש מוגבל. למרות שכיום נחשב לאלגוריתם לא-בטוח, חשיבותו ההיסטורית נותרה בעינה מאחר שהטכניקות שיושמו באלגוריתם נלמדות כיום באקדמיה ומשמשות השראה ובסיס למרבית האלגוריתמים הסימטריים המודרניים. כיום הוחלף DES באלגוריתם AES שהפך ב-2001 לתקן ההצפנה הרשמי של ארצות הברית. אלגוריתמים סימטריים נוספים הם 3DES, IDEA, FEAL, SAFER, RC5, RC4, ו-Serpent.

הצפנה סימטרית סובלת ממספר בעיות:

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

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

סודיות מושלמת

ערך מורחב – סודיות מושלמת

בשנת 1949 הראה קלוד שאנון, בשיטות השאולות מתורת האינפורמציה, שיטת הצפנה (סימטרית) "מושלמת" המכונה פנקס חד-פעמי (One time pad). שיטה זו המבוססת על צופן ורנם, בה מצפינים מחרוזת מסר על ידי חיבור XOR של סיביות המסר בזו אחר זו, עם מפתח שנבחר באופן אקראי. אם המפתח אקראי "אמיתי" וחד-פעמי ובאורך המסר המיועד להצפנה, הצופן יהיה בעל סודיות מושלמת (Perfect Secrecy) והוא בטוח ללא סייג. אין שום דרך לשחזרו ללא המפתח (אפילו במקרה שמנחשים מפתח, אין דרך לדעת האם הוא המפתח הנכון). פנקס חד-פעמי מחייב שימוש יחיד במפתח. המפתח חייב להיות ממקור אקראי אמיתי (בניגוד למספרים פסבדו אקראיים המיוצרים על ידי מחשב).

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

הצפנה א-סימטרית

ערך מורחב – מפתח ציבורי

מערכת טיפוסית של הצפנת מפתח ציבורי

סוג חדש יותר של הצפנה הוא הצפנה אסימטרית. רעיון ההצפנה האסימטרית עלה לראשונה ב-1976 במאמרם המפורסם של ויטפילד דיפי ומרטין הלמן הנחשבים להוגי השיטה וממציאיה. בהצפנה זו, בניגוד להצפנה סימטרית, נעשה שימוש בשני מפתחות, האחד נקרא מפתח פומבי איתו מצפינים את המסר. מכאן שמה של השיטה – Public Key Cryptography. המפתח הפומבי אינו נשמר בסוד אלא גלוי ונגיש לכל. לא ניתן לשחזר את המסר המוצפן באמצעות שימוש במפתח זה. המפתח השני נקרא מפתח פרטי שעליו להישמר בסוד בידי המקבל ורק באמצעותו ניתן לפענח את המסר המוצפן.

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

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

חסרונותיה של השיטה האסימטרית נעוצים באורך מפתחות ההצפנה, הגדל בהתאם לכוח המחשוב (נכון לינואר 2005 נעשה שימוש במפתחות באורך של 2048 סיביות כסטנדרט). בשל כך כוח המחשוב הנדרש להצפנה אסימטרית גדול משמעותית מהצפנה סימטרית. עקב כך, מקובל שההצפנה האסימטרית אינה מהווה חלופה להצפנה הסימטרית אלא משלימה אותה. מערכות הצפנה מתקדמות מנצלות את שתי השיטות תוך ניצול יתרונותיהן להפקת מרב התועלת. בין האלגוריתמים אסימטריים המפורסמים נמנים: RSA, DSA, אל-גמאל,רבין וECC. האחרונה היא סוג חדש של מערכת מפתח-פומבי הנקראת הצפנה מבוססת עקומים אליפטיים, לדעת מומחים רבים, השימוש בה מאפשר הקטנת מפתחות ההצפנה במידה ניכרת (בסדר גודל של 256 סיביות) מבלי לאבד מבטיחותה ובכך לייעל את מערכת ההצפנה. עובדה זו אטרקטיבית במיוחד עבור מפתחי חומרה ייעודית להצפנה, שמטבע הדברים מוגבלת בכוח המחשוב ובכמות הזיכרון.

קריפטאנליזה מודרנית

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

בעבר נטו מפתחי אלגוריתמים קריפטוגרפיים לשמור בסוד את פרטי האלגוריתם. אולם כיום מקובל לאמץ את עקרון קרקהופס הקובע ששמירת אלגוריתם הצפנה בסוד אינה מהווה חלופה לבטיחותו ושמירתו בסוד לאורך זמן כמעט בלתי אפשרית. באנלוגיה למנעול צירופים, הסתמכות אך ורק על מנגנון נעילה סודי, אינה חכמה כיוון שאם נחשף המנגנון המנעול כולו הופך לחסר תועלת. מאידך אם התגלה צירוף סודי, יש צורך רק להחליף צירוף על מנת להבטיח סודיות, אין צורך בקניית מנעול חדש. גם בעת המודרנית הוכרזו מספר אלגוריתמי הצפנה כסודיים. אלגוריתם Skipjack שפותח על ידי NSA נשמר בסוד עד 1998. צופן זרם RC4 היה סוד מסחרי כשהומצא ב-1987 על ידי רונלד ריבסט במעבדות RSA. אולם בדרך כלשהי הצליח מישהו להנדס לאחור את האלגוריתם ופרטיו דלפו באופן אנונימי לרשת האינטרנט והפכו במהרה לנחלת הכלל.

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

מלבד פנקס חד-פעמי, לא ידוע על אלגוריתם בלתי שביר. כל אלגוריתם ניתן לשבירה עם די זמן וכוח חישוב. הבחירה היא תמיד בין קלות יישום לעומת בטיחות. קיימות שיטות ניתוח רבות, בחלקן מנתח הצופן (המכונה לעתים "התוקף"), מחזיק בצופן בלבד ועליו לגלות את הטקסט הקריא או המפתח מתוכו כמו התקפת מוצפן-נבחר, בחלקן המתקיף מחזיק בידיו חלק מהטקסט המקורי שהוצפן, במקביל לצופן שהתקבל ממנו (התקפת גלוי ידוע, known plaintext attack) ובחלקן המתקיף מסוגל לבחור בעצמו בטקסט שהוא מעוניין, כמקור להצפנה וללמוד את תוצאותיו (התקפת גלוי נבחר, chosen plaintext attack). בחירת טקסט כאסטרטגיה לשבירת הצופן אפשרית בעולם האמיתי בהרבה מערכות.

למעשה, הדעה הרווחת היא כי מרבית האלגוריתמים הידועים שזכו לביקורת ובדיקה מדוקדקת של מומחים, אכן בטוחים. הסיבה שמערכות רבות נפרצו או כשלו לא נבעה ישירות מליקויים כלשהם באלגוריתמים שעליהם התבססו, אלא בשל כשלים או שגיאות אנוש באופן יישום אותם אלגוריתמים, שנבעו בין היתר מבורות או מרשלנות ואי-הקפדה על נוהלי בטיחות. יותר קל להשיג מידע באמצעות ציתות, מתן שוחד או גניבת מפתחות מאשר לפרוץ אלגוריתם. כדי להקים מערכת אבטחה, תחילה יש להבין היטב את האלגוריתמים המשמשים אותה ובמיוחד את תכונותיהם, פגיעותם ומגבלותיהם. ולוודא כי המערכת כמכלול אינה חדירה או מדליפה מידע עקיף המסכן את בטיחותה. כגון מידע תזמון (timing). בגרסת WAP (פרוטוקול אבטחה סלולרי) המקורית לדוגמה, התגלתה פרצה בטיחותית חמורה שנבעה מאופן יישום אלגוריתם RC4 וגרמה לדליפת מידע שאיפשר לפרוץ את המערכת בקלות.

אנליזה של אלגוריתמים סימטריים

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

1. כוח גס (Brute Force): אפשר לקרוא לה השיטה הנאיבית, חיפוש ממצה של לפחות מחצית מטווח המפתחות האפשריים במקרה הממוצע עד למציאת המפתח שאיתו נעשה שימוש. כשמה זוהי שיטה ברוטלית ולא יעילה אולם עם מספיק זמן וכוח חישוב תביא בסופו של דבר לתוצאות, אם כי סיבוכיותה אינה מעשית ברוב המקרים. למעשה ממציאי אלגוריתמים סימטריים שואפים כי האלגוריתם שלהם יהיה טוב עד כי רק כוח גס מסוגל לפצחו. הוכחה כי אלגוריתם מסוים ניתן לשבירה אך ורק באמצעות כח גס מהווה הוכחת איכות, כיוון שניתן לשלוט ביעילותה על ידי בחירת נכונה של גודל המפתח בסיביות. לשם המחשה, כוח גס כנגד צופן DES מצריך סריקה של לפחות $2^{55}$ מפתחות במקרה הממוצע, שהוא כמחצית מטווח המפתחות האפשרי. עד 1998 שבירת צופן DES הייתה אפשרית רק על ידי חומרה ייעודית שעלותה יקרה ונמשכה בדרך כלל מספר ימים. ב-2008 פרסמה חברת SciEngines שרת ייעודי יחיד עם חומרה מותאמת, בעל תפוקה של 26 מיליארד מפתחות בשנייה, המסוגל לפרוץ את DES בפחות מיום אחד. ניתן ליישם כח גס גם באמצעות חישוב מבוזר, גיוס זמן בטלה של מעבדים על בסיס התנדבותי, הזמין כיום באמצעות רשת האינטרנט, המאפשר להגיע להשגים אף טובים יותר. ב-1999 נפרץ DES ב-23 שעות בלבד באמצעות 100,000 מחשבים ביתיים. כמובן שכיום ניתן לפרוץ את DES בעלות נמוכה ובזמנים טובים יותר.
2. קריפטאנליזה לינארית: שיטת שבירת צופן המיוחסת לקריפטוגרף היפני מיצורו מצואי. בשיטה זו ניתן לפצח את DES ב-$2^{43}$ ניסיונות הצפנה בהינתן $2^{43}$ טקסטים מוצפנים שמקורם ידוע. קריפטאנליזה לינארית היא התקפת גלוי ידוע, המתמקדת בחיפוש אחר קירובים לינאריים היעילים ביותר המתאימים למספר ספציפי של סבבים בצופן המותקף, עם שיעור הצלחה גבוה מחצי, תוך ניצול חולשות בתיבות ההחלפה (S-box) של האלגוריתם. כל ביטוי כזה מאפשר לחלץ סיבית מפתח אחת באמצעות תהליך הסתברותי של חיפוש התאמות בכמות גדולה של טקסט מוצפן ומקור ידועים ובסופו של תהליך ניחוש המפתח כולו. למרות שזהו שיפור משמעותי לעומת כח גס, השיטה אינה יעילה עבור מחשב ממוצע בהתחשב בכמות הטקסט הדרושה.
3. קריפטאנליזה דיפרנציאלית: הומצאה על ידי אלי ביהם ועדי שמיר (מכון ויצמן למדע 1980)‏‏. זו שיטה רבת עוצמה לניתוח אלגוריתמים סימטריים מכל סוג כמעט. בשיטה זו נבחנת מידת ההשפעה של הבדלים בקלט על פלט הצופן. בשיטה זו ניתן לפצח את DES ב-$2^{47}$ ניסיונות, אף בלא ידיעת מקור הצופן. כמו כן נפרצו בשיטה זו ב-1989 וב-1991 כל וריאציות צופן FEAL (ארבעה ושמונה סבבים). הוכח גם שגרסאות מתקדמות יותר של האלגוריתם FEAL-N וכן FEAL-NX שפותחו עקב כך ניתנות לשבירה (עד 31 סבבים) בפחות מהזמן הדרוש לכוח גס. ובכך הקיץ הקץ על האלגוריתם ‏‏.

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

ניתוח אלגוריתמים א-סימטריים

אלגוריתמים המבוססים על מפתח-פומבי נשענים בעיקר על מספר מצומצם של בעיות מתמטיות קשות מאוד. בהן נמנות בעיית פירוק לגורמים של מספר שלם (עליה מבוססת, למשל, הצפנת RSA), בעיית הלוגריתם הדיסקרטי (עליה מבוססת הצפנת אל-גאמל) ובעיית הוצאת שורש ריבועי מודולו מספר פריק (עליה מבוססת הצפנת רבין). בעיות אלו מאפשרות יישום פונקציות חד-כיווניות, במובן שהן קלות לחישוב בכיוון אחד אולם קשות ביותר לשחזור בכיוון ההפוך. במיוחד מדובר על פונקציות חד-כיווניות עם דלת סתרים (Trap-door), שהיא פונקציה חד-כיוונית שקל לחשבה גם בכיוון ההפוך אם קיים "מידע נסתר" נוסף (למשל בבעית הפירוק לגורמים, דלת הסתרים היא הגורמים הראשוניים או חלקם). על פונקציה חד-כיוונית מבוססים מרבית האלגוריתמים האסימטריים, כאשר דלת הסתרים היא המפתח הפרטי. אף שמשערים כי הפונקציות בהן משתמשים היום בפועל הן חד-כיווניות, מעולם לא ניתנה לכך הוכחה פורמלית, ושאלת קיומן של פונקציות חד-כיווניות קשות באופן ודאי היא בעיה פתוחה חשובה במדעי המחשב (בפרט, תשובה חיובית לשאלה זו תהווה הוכחה לכך ש-P שונה מ-NP, מה שישים קץ לשאלה הפתוחה המרכזית במדעי המחשב).

טרם נמצא אלגוריתם יעיל המסוגל לפתור בזמן ריצה פולינומי את אחת מהבעיות שבבסיס האלגוריתמים האסימטריים הנפוצים בימינו ובכך לסכנם (ובפועל, להוציאם מכלל שימוש). קיימים עם זאת אלגוריתמים רבים לפתרון בעיות יסודיות אלו, היעילים במידה ניכרת מכוח גס. הדוגמה הידועה ביותר היא בעיית פירוק לגורמים עתיקת היומין, שמתמטיקאים רבים וטובים התחבטו בה. האלגוריתם הטוב ביותר הידוע כיום לפתרונה הוא נפת שדה מספרים.‏‏ בנובמבר 2005 הצליח צוות מתמטיקאים לפרק לגורמים את RSA-200 (בגודל 663 סיביות) מתוך מספרי האתגר של מעבדות RSA במאמץ שנמשך כמעט שלוש שנים, תוך שימוש במספר גדול של מחשבים שעבדו במקביל. במאי 2007 הצליח צוות מתמטיקאים לפרק לגורמים את המספר $\ 2^{1039}-1$ (המכונה מספר מרסן) המספר הגדול ביותר שפורק לגורמים נכון להיום (בגודל 1039 סיביות), במאמץ שנמשך קרוב לשנה תוך שימוש בגרסה מותאמת של נפת שדה המספרים. למרות שהמספר אינו מהסוג הנפוץ בשימוש במערכות מפתח פומבי דוגמת RSA, הדעה הרווחת היא כי בקרוב תמצא הדרך להרחיב את השיטה לפירוק מספרים בגודל 1024 סיביות מהסוג הנפוץ במערכות מפתח פומבי רבות בימינו.

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

פרימיטיבים קריפטוגרפיים

פרימיטיב קריפטוגרפי הוא הגדרה לאלגוריתם קריפטוגרפי שייעודו ספציפי למטרה או יעד מוגדר. אלגוריתם AES הוא פרימיטיב קריפטוגרפי שתפקידו להצפין מידע בשיטה סימטרית. פרימיטיבים אחרים הם RSA, פונקציית גיבוב SHA-1 וכן DSA. מהות הרעיון הוא שבהקמת מערכת אבטחת מידע שלמה, אין די באלגוריתם אחד דהיינו בפרימיטיב קריפטוגרפי אחד, אלא משלבים מספר אלגוריתמים שלכל אחד מהם תפקיד אחר. יחדיו הם משלימים זה את זה למערכת שלמה. על כן נודעת חשיבות רבה לבדיקת המאפיינים והיחסים שבין הפרימיטיבים השונים, על מנת לוודא כי השילוב ביניהם בטוח ואינו מכיל פרצות. לעתים אי-הבנה באשר למהות פרימיטיב מסוים והניסיון לשלבו במערכת או להשתמש בו באופן שלא יועד לו, עשוי לפגוע בבטיחות המערכת כולה. לדוגמה פונקציית גיבוב טובה ליצירת ערכים ייחודיים, אולם אינה טובה כשלעצמה לצורך הצפנה. יתרונה הברור בא לידי ביטוי במערכת הצפנה דוגמת PGP בה יש צורך בערך חד-כיווני של המידע המשמש תווית לצורך החתימה על המסר באמצעות חתימה דיגיטלית.

פרוטוקולים ומנגנונים קריפטוגרפיים

ערך מורחב – פרוטוקול קריפטוגרפי

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

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

קריפטוגרפיה ותורת הקוונטים

במהלך המאה ה-20 החל להתפתח בקצב מהיר ענף החישוביות הקוונטית, שעלולות להיות לו השלכות קריטיות על הקריפטוגרפיה המודרנית. אם ניתן יהיה לבנות מחשב קוונטי בעל יכולת גידול (סקאלבילי), אזי למעשה מרבית האלגוריתמים האסימטריים כגון RSA ודומיו יצאו מכלל שימוש. יהיה צורך בשדרוג מקיף של כל מערכות ההצפנה. זאת בשל קיומם של אלגוריתמים קוונטיים שמאפשרים פיצוח צפנים אילו בזמן פולינומי, לאור היכולת לבצע חישובים בצורה מהירה יותר מאשר במחשב "רגיל".

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

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

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

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

הצפנה קוונטית

ערכים מורחבים – הצפנה קוונטית, החלפת מפתחות קוונטית

על פי תורת הקוונטים, ובפרט על פי עקרון אי הוודאות של הייזנברג, לא ניתן לבצע 'מדידה' מבלי להשפיע על המצב של האובייקט הנמדד. המשמעות של עקרון זה היא שאדם המאזין לשיחה, בהכרח משפיע עליה, ומכאן שניתן לזהות את ההאזנה. בעקרון זה נעשה שימוש להעברת מידע בצורה לגמרי מאובטחת - המזהה כל ניסיון להאזין למידע. בשנת 1984 פותח פרוטוקל ראשון המיישם עקרון זה על-מנת לבצע החלפת מפתחות קוונטית (QKD) באופן בטוח, ולאחריו פותחו מספר פרוטוקולים נוספים אשר עושים שימוש בשיטות שונות, דוגמת שימוש במצבי EPR). ניתן לראות בפרוטוקולים אלו את המקביל הקוונטי של פרוטוקול דיפי-הלמן. בפרוטוקולים אלו הסודיות המתקבלת היא "מושלמת" במובן תורת האינפורמציה. כל ניסיון של גורם זר להתערב בפרוטוקול מסתיים בגילויה של התקיפה. אם לא נתגלתה תקיפה, מוכח כי כמות האינפורמציה שזלגה אל גורם שלישי היא זניחה.

חוקיות וזכויות שימוש

מטבע הדברים, סגולותיה של הקריפטוגרפיה, ככלי לשמירה על פרטיות, מנוצלות לרעה על ידי גורמים זדוניים כמו ארגוני פשע, טרור וריגול. מאז ומתמיד ממשלות וגורמי ביטחון במדינות שונות גילו עניין רב בהתפתחויות בתחום זה. בכל מדינה כמעט קיים גוף האחראי על השימוש בהצפנה, מחקר ופיתוח וכן ניטור וניתוח של חומרים מוצפנים שקיים חשש שהם מסכנים את ביטחונה הלאומי. גם ארגוני זכויות אדם ברחבי העולם מגלים עניין בתחום זה בשל תרומתו לשמירת הפרטיות. בשל כך היו בעבר בארצות הברית מספר אירועים שערורייתיים, הקשורים בנושאים חוקתיים בתחום זה. ישנן מדינות (בהן ישראל) שבהן עד היום קיימות מגבלות חוקיות לעיסוק בקריפטוגרפיה ובכל מה שקשור אליה. בישראל קיים החל מ-1974 "צו צופן" ([2], תוקן ב-1998) המחייב כל גורם המעוניין לעסוק בהצפנה בקבלת רישיון עיסוק בהצפנה ממנכ"ל משרד הביטחון (בעבר מקצין קשר ראשי בצה"ל). במדינות אחרות (כמו ארצות הברית), העיסוק בקריפטוגרפיה לא מוגבל מקומית אך קיימות מגבלות ייצוא של חומרים קריפטוגרפיים מחוץ לתחומי המדינה. למעשה בארצות הברית קריפטוגרפיה סווגה כסוג של "תחמושת" בדומה לטנק או טיל בליסטי, ובעבר אף נאסר שימוש בהצפנה חזקה בארצות הברית, כאשר הפיקוח על ההצפנה היה באחריות הסוכנות לביטחון לאומי (NSA) של ארצות הברית. NSA הנו הארגון הממשלתי הגדול והמצויד ביותר בעולם שעוסק בקריפטוגרפיה ומעסיק עשרות אלפי עובדים. מטרתו העיקרית ניטור, פענוח וחשיפת תשדורות או מידע דיגיטלי אחר ברחבי העולם, שלהם זיקה לביטחונה הלאומי של ארצות הברית. מדינות אחרות (בעיקר מדינות ארופיות) נוקטות בגישה יותר ליברלית בכל הקשור להצפנה.

על אלגוריתמים קריפטוגרפיים אפשר להגן (במדינות מסוימות, כגון ארצות הברית) בפטנטים. על המימוש שלהם אפשר להגן בזכויות יוצרים (אולם אם המפרט מפורסם, כל אחד יכול לממש אותם מחדש). אפשר לנסות גם לשמור אותם כסוד מסחרי. בארצות הברית, בקנדה ובמדינות רבות אחרות רשומים מאות פטנטים על סוגים שונים של אלגוריתמים קריפטוגרפיים. לדוגמה אלגוריתם RSA נרשם כפטנט שתוקפו פג בשנת 2000. בשל המגבלה שנוצרה מהפטנט נאלצה ממשלת ארצות הברית ליצור תקן חתימה אלקטרונית חלופי בשם DSA שלא מוגן בפטנטים‏. אי הבהירות סביב הפטנטים שעל ההצפנה בעקומים אליפטיים (ר' בהמשך) היא אחת הסיבות לחוסר הפופולריות שלהם^{[דרוש מקור]}.

בארצות הברית (וגם בישראל) רשומים מספר פטנטים על אלגוריתמים שונים להצפנה. החברה האמריקאית RSA מחזיקה כיום במספר פטנטים הקשורים לאלגוריתמי הצפנה שונים. למרות ששם החברה הינו "RSA", הפטנטים שבבעלותה כיום אינם בהכרח קשורים לאלגוריתם המקורי. החברה הקנדית Certicom מחזיקה בכמאה ועשרים פטנטים בהיבטים שונים של ECC (הצפנת עקום אליפטי) בארצות הברית ובקנדה בלבד.

החל מאמצע שנות ה-90 של המאה העשרים היו כמה תחרויות של ממשלות לבחירת פרימיטיבים קריפטוגרפיים חדשים: תחרות AES של מכון התקנים האמריקאי‏, ‏NESSIE של האיחוד האירופי‏,‏ CRYPTEC ביפן‏. בכל המקרים הללו אחד מהתנאים היה שהזוכים ישחררו את התוכנה ללא מגבלות שימוש כלשהן.

אזכורים בספרות

כתב החידה מתוך ספרו של ז'ול ורן "מסע אל בטן האדמה"

• קיימים אזכורים רבים בספרות לאורך השנים.
• הסיפור "חיפושית הזהב" (אדגר אלן פו) מתאר פיצוח של צופן החלפה, על ידי ניתוח תדירויות.
• הספר "מסע אל בטן האדמה" (ז'ול ורן) נפתח בקבלת כתב חידה הכתוב בסימנים לא מובנים, אשר מעורר את תחילת ההרפתקה.
• בספר "עמק הפחד" ובסיפור הקצר "תעלומת הדמויות המרקדות" (ארתור קונן דויל) מתמודד שרלוק הולמס עם כתבי חידה ומפצח אותם.
• בסדרת הספרים "הארי פוטר" (ג'יי קיי רולינג), שמו של לורד וולדמורט הוא אנגרמה של הדמות טום ונדרולו רידל.
• בספר "צופן דה וינצ'י" (דן בראון) משולבים מספר קטעים קריפטוגרפיים וסטנוגרפיים לרבות אנגרמות וכתב ראי. הספר "מבצר דיגיטלי" מאת אותו סופר עוסק בהצפנה (אך כולל טעויות רבות ‏[3]‏).
• הספר זוכה פרס הפוליצר "גדל, אשר, באך" (דאגלס הופשטטר) מכיל מספר רב של חידות מילים מסוגים שונים ה"מוחבאים" כחלק מהטקסט. בנוסף, מכיל הספר קטעים הכתובים בשפה לא ידועה (לא ברור האם קטעים אלו בעלי משמעות או לא).

ראו גם

• סטגנוגרפיה
• כתב היד של וויניך
• דיו סתרים

לקריאה נוספת

• ברוס נורמן, מלחמת הצפנים, תל אביב: הוצאת מערכות, 1978.
• סיימון סינג, סודות ההצפנה, תל אביב: הוצאת ידיעות אחרונות, 2003.

• A. S. Tanenbaum, Computer Networks, 4th ed. (Prentice Hall, 2003).

קישורים חיצוניים

• מבוא להצפנה ואבטחת מידע, מבוסס על קורס מאת פרופ' שלמה קיפניס.
• אתר אית"ן ללימוד הצפנה, אתר ללימוד מקיף של סוגי ההצפנה השונים: PGP, RSA, SSH ועוד
• ספר/מדריך מקוון המגדיר מונחים בקריפטוגרפיה, מכיל השוואות בין סכימות קריפטוגרפיות ומספק דוגמאות מוחשיות (אנגלית)
• הספר Handbook of Applied Cryptography, לשימוש פרטי בלבד.
• האתר הבינלאומי של PGP
• הסבר על איך עובדת PGP (אנגלית)
• הסדר העיסוק באמצעי הצפנה, מדינת ישראל, משרד הביטחון אגף הפיקוח על היצוא הביטחוני, פיקוח ורישוי אמצעי הצפנה.
• ערכת כלים קריפטוגרפיים של חטיבת אבטחת מחשבים (CSD) של NSA, כולל מידע מפורט על שלל אלגוריתמים קריפטוגרפיים למטרות שונות שאומצו על ידי ממשלת ארצות הברית (FIPS) להגנה על מידע מסווג ולא מסווג ונבדקו ואושרו לשימוש על ידי מומחי ממשל בכירים.
• יפתח הייטנר, קריפטוגרפיה - לא רק הצפנה

הערות שוליים

ערך מומלץ