דוגמאות לקבוצות.
דוגמה נוספת.
כל שלוש הקבוצות הללו זהות, אף על פי שהן נוצרו באמצעות הגדרות שונות: ציון כל איברי הקבוצה (הכי יעיל במקרה של קבוצות בעלות מספר קטן של איברים); או על ידי ציון כל אברי הקבוצה, גם אם הם מופיעים יותר מפעם אחת (סדר ההופעה ומספר המופעים אינו חשוב ואינו משפיע על הגדרת הקבוצה); או על ידי הגדרה חד ערכית של אברי הקבוצה (יעיל במקרה של מספר רב של איברים), שניתן להגדיר עבורם חוק או הגדרה.
סימונים והגדרות.
הפרדוקס של ראסל הבהיר שההגדרה האינטואיטיבית של קבוצה, איתה התחלנו ערך זה, מובילה לסתירה פנימית (אנטינומיה). בעקבות זאת ניתן לתורת הקבוצות, שהיא ענף המתמטיקה העוסק בחקר הקבוצות, ביסוס אקסיומטי, לשם היחלצות מסתירה זו.
איחוד וחיתוך של קבוצות.
החיתוך של אוסף של קבוצות הוא קבוצה שמורכבת מהאיברים ששייכים לכל הקבוצות הנחתכות. החיתוך של שתי קבוצות A,B מסומן ב-formula_19. חיתוך של משפחה
formula_20 מסומן ב-formula_21. ולפעמים בקיצור formula_22.
האיחוד של אוסף של קבוצות הוא קבוצה שמורכבת מהאיברים ששייכים ללפחות אחת מבין הקבוצות המאוחדות. האיחוד מסומן בדומה לחיתוך, פרט לזה שאת הסימנים formula_23 מחליפים formula_24.
הפרש של שתי קבוצות A,B הוא קבוצת האיברים של A שאינם שייכים ל-B, ומסמנים אותו ב-formula_25 או formula_26. ההפרש מאפשר להגדיר גם את ההפרש הסימטרי.
קריפטוגרפיה
קריפטוגרפיה (בעברית: תּוֹרַת כְּתִיבַת הַסֵּתֶר) היא ענף במתמטיקה ובמדעי המחשב העוסק במחקר ופיתוח שיטות אבטחת מידע ותקשורת נתונים על רובדיהם השונים, בסביבה פתוחה הנגישה לצד שלישי המכונה "אויב", או "יריב" פוטנציאלי. התחום מאגד תחתיו פיתוח ואנליזה של פרוטוקולים המתמודדים בהיבטים שונים של אבטחת מידע בנוכחות צד שלישי, מהם בנוסף לסודיות, הרשאת גישה, סיסמה, הוכחת ידיעה, פרוטוקול אתגר-מענה, מנגנוני חתימה דיגיטלית, חלוקת סוד, חישוב רב משתתפים בטוח, אימות זהויות, מניעת הכחשה ועוד.
מערכת הצפנה משתמשת באבני בניין קריפטולוגיות כגון צופן סימטרי, צופן זרם, מפתח פומבי, פונקציות גיבוב, קוד אימות מסרים, מחולל פסבדו אקראי וכדומה.
קריפטוגרפיה מודרנית משתלבת בתחומי מחקר אחרים כמו מתמטיקה, סטטיסטיקה והסתברות, תורת האינפורמציה, מדעי מחשב והנדסת אלקטרוניקה. יישומיה רבים ומגוונים וכוללים בין היתר, אבטחת רשתות תקשורת, תקשורת סלולרית, חומת אש, מסופי משיכה, כרטיסי אשראי, דואר אלקטרוני, מסחר אלקטרוני, הצבעה ממוחשבת ועוד.
השם "קריפטוגרפיה" מקורו במילה היוונית "קריפטו" (κρυπτός) שמשמעותה נסתר או אומנות ההסתרה, ו"גרפיה" (γράφω) שמשמעותה "כתיבה". בתרגום חופשי נעשה שימוש בשם באופן חליפי למונח קריפטולוגיה שפירושו תורת ההסתרה (Crypto-logia, κρυπτός-λογία), אם כי משמעותו רחבה יותר מתחום ההצפנה בלבד.
מונחים כלליים.
במובן הבסיסי, המונח הצפנה (באנגלית: encryption) מתאר הסתרת משמעותו של מסר קריא באמצעות פונקציה שמקבלת כפרמטר מפתח הצפנה והופכת את המסר לרצף של סימנים בלתי מובן לאיש. שחזור הטקסט המוצפן למצבו הקריא באמצעות פונקציה הופכית מתאימה עם מפתח הפענוח, קרוי פענוח (באנגלית: decryption). המונח צופן (Cipher) מתייחס לאלגוריתם הצפנה בדרך כלל במחשב, כאשר קלט האלגוריתם נקרא תַּמְלִיל פָּשׁוּט או טקסט גלוי (באנגלית: Plaintext) ואילו פלט האלגוריתם נקרא תַּמְלִיל מֻצְפָּן או טקסט מוצפן (באנגלית: Ciphertext). פעולת אלגוריתם ההצפנה נשלטת על ידי מפתח ההצפנה הסודי הידוע רק לשולח ולמקבל. בשפה העברית משמשת המילה צופן גם כשם עצם לכתב סתר או קוד. שיטות הסתרת מידע שאינן עושות שימוש במפתח הצפנה קרויות סטגנוגרפיה.
בעבר שימש המונח קריפטוגרפיה כמעט באופן בלעדי לתיאור הצפנת מסרים. אולם בעידן המודרני התחום הלך והתרחב והוא משמש כיום לתיאור ענף מדעי רחב היקף העוסק בהיבטים השונים של אבטחת המידע, אלגוריתמים קריפטוגרפיים, פרוטוקולים ומנגנוני אבטחת מידע, פרוטקולי אימות זהויות, שיטות הבטחת שלמות ופסבדו-אקראיות. בניסוח פורמלי, משמשת המילה קריפטוגרפיה לתיאור שיטות יישום ההצפנה ואילו קריפטואנליזה מתמקדת בחקר השיטות לשבירתה. את תחום המחקר המאגד את שניהם מכנים קריפטולוגיה. בניסוח לא פורמלי, ניתן לעשות שימוש במילה קריפטוגרפיה כדי לתאר את הענף כולו.
במערכת תקשורת טיפוסית כמו רשת האינטרנט הקריפטוגרפיה משתלבת יחד עם רכיבי תקשורת נוספים כמו איפנון, תיקון שגיאות ודחיסה. התרשים משמאל מתאר באופן כללי את השלבים בהם עובר מידע הזורם בערוץ תקשורת מצד אחד לצד השני ואת מיקומה של הקריפטוגרפיה במערכת כזו, בדרך כלל בין שלב קידוד המידע (כגון דחיסה) לבין קידוד הערוץ (תיקון שגיאות). קריפטוגרפיה מודרנית מטפלת בשלושה נושאים עיקריים:
בנוסף קיימים תהליכים נלווים כגון מחולל פסאודו-אקראי המשמש בין היתר להכנת מפתחות הצפנה, פונקציות גיבוב וכדומה ותהליכים נוספים שאינם בהכרח קריפטוגרפיים. השאיפה היא שתהליכים אלו יהיו שקופים מבחינת המשתמש, כאשר משתמש מתחבר לשרת או מבצע עסקה מקוונת, ההכנות הדרושות נעשות ברקע מבלי שיחוש בכך, מלבד הדרישה מעת לעת לספק פרטי זיהוי כלשהם כמו סיסמה, מספר כרטיס וכדומה.
רקע היסטורי.
הצפנה ככלי לקידוד והסתרת מידע הייתה קיימת משחר ההיסטוריה. עד לעשורים האחרונים מקובל להתייחס אליה כאל הצפנה קלאסית או הצפנת 'עט ונייר'. כלומר שיטות הצפנה לקסיקוגרפיות הפועלות על סימנים כגון אותיות וספרות ומיושמות ידנית או באמצעים מכניים פרימיטיביים כמו גליל או מכונת כתיבה או בשיטות סטגנוגרפיות. התפתחותה של הקריפטוגרפיה הואצה בראשית המאה העשרים עם הופעת מנגנוני הצפנה מכניים ואלקטרו-מכניים מורכבים ומסובכים יותר ויותר, הנקראים מכונות הצפנה מבוססות רוטור, בראשן האניגמה. הקריפטוגרפיה המודרנית המוכרת לנו כיום החלה עם המצאת המחשבים, שיטות ההצפנה הפכו למתמטיות יותר ויותר באופיין ומורכבותן הפכה למסובכת מדי לביצוע באופן ידני, עד שהפכה נחלתם הבלעדית של המחשבים.
במקביל התפתחה הקריפטואנליזה. מה שהחל כאמנות פיצוח קודים והמשיך עם גילוי הניתוח הסטטיסטי ככלי יעיל לשבירת צפנים. היכולת לקרוא תשדורות מוצפנות השפיע רבות על מהלך ההיסטוריה. אפשר לציין כדוגמה את מברק צימרמן שגרם להתערבותה של ארצות הברית במלחמת העולם הראשונה. או השפעת פיצוח הצפנים הנאציים בידי הבריטים, על מאזן הכוחות במלחמת העולם השנייה.
בעבר שימשה הקריפטוגרפיה הקלאסית בעיקר ממשלות, צבאות, דיפלומטים ומרגלים. שני אירועים לכאורה לא קשורים שאירעו בשנות השבעים של המאה העשרים בסמיכות רבה, הביאו למפנה העיקרי ותרמו יותר מכל להפיכתה למודרנית כפי שהיא מוכרת כיום; הפצת DES כתקן הצפנה והמצאת RSA. קריפטוגרפיה מודרנית התפתחה בשני מישורים מקבילים אילו: הצפנה סימטרית והצפנה א-סימטרית.
בעשורים האחרונים של המאה העשרים ההצפנה עברה מהפך משמעותי מסוג של מיומנות שהיא נחלתם של מעטים, שבעיקרה הייתה אוסף פעולות אד הוק שמסתמכות על התחכום של מפתח הצופן למדע מבוסס היטב שנשען על יסודות תאורטיים מוצקים. אפשר לחלק את הפרדיגמות המייחדות פיתוח צופן בקריפטוגרפיה המודרנית לעומת הקלאסית לשלושה צעדים עיקריים:
לצעדים אילו חשיבות הן בפיתוח הצופן כדי להבהיר מה בעצם מנסים להשיג באמצעות האלגוריתם. הן בשימוש בו, כיצד ואיפה להשתמש בו בצורה בטוחה מבלי להיכשל בשימוש לא ראוי או שימוש שלא יועד לו והן במחקר ובדיקת טיב האלגוריתם לעומת אחרים.
הצפנה סימטרית.
הצפנה סימטרית היא הוותיקה ביותר ושורשיה החלו עם ההצפנה הקלאסית לפני מאות שנים. הצפנה סימטרית היא אלגוריתם הצפנה שעושה שימוש באותו מפתח הן להצפנת המידע והן לפענוחו. כלומר בשיטה הסימטרית כדי שניתן יהיה להעביר מידע סודי בין הצדדים המתקשרים, שניהם נדרשים להחזיק באותו מפתח הצפנה. צופן סימטרי יכול להיות מבוסס על שתי הגישות העיקריות להצפנה סימטרית צופן זרם או צופן בלוקים כשלכל אחת מהן יתרונות וחסרונות והן מתאימות לצרכים שונים. באופן כללי יתרונותיה של ההצפנה הסימטרית הם ביעילות החישובית ובכוח המחשוב הנמוך יחסית הדרוש ליישומה לעומת הצפנה אסימטרית. למשל נכון לשנת 2015 תקן ההצפנה המתקדם נחשב לאלגוריתם הסימטרי המועדף הן מהיבט של ביטחון והן מהיבט של יעילות אף על פי שקיימים אלגוריתמים מהירים מעט יותר. ביישום ממוטב בחומרה תפוקתו היא כמעט 700 MB לשנייה לליבה אחת. התקן מגדיר מפתח הצפנה באורך של 256 סיביות כבטוח לכל צורך מעשי לתקופה הקרובה.
אף על פי שקיימים אלגוריתמים סימטריים רבים, אלגוריתם DES הוא הדוגמה הקלאסית הטובה ביותר לצופן סימטרי מודרני. DES היה לאלגוריתם הסימטרי הראשון שהופץ בקנה מידה גדול ואף הפך לתקן הצפנה רשמי, שימש בעיקר בתחום הבנקאות והוא עדיין בשימוש מוגבל בגרסה המשולשת. אף על פי שכיום לא נחשב לאלגוריתם בטוח, חשיבותו ההיסטורית נותרה בעינה מאחר שהטכניקות שיושמו בו נלמדות כיום באקדמיה ומשמשות השראה ובסיס לאלגוריתמים סימטריים מודרניים רבים.
אלגוריתמים נוספים הם 3DES, IDEA, FEAL, SAFER, RC5, RC4, Blowfish, ARIA וסרפנט.
להצפנה סימטרית מספר חסרונות: