איך לתרגל שאלות קריפטוגרפיה במבוא למדעי המחשב?

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

כמה שאלות קריפטוגרפיה יש במבוא למדעי המחשב?

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

מה חשוב לדעת על קריפטוגרפיה לקראת מבחן במבוא למדעי המחשב?

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

מבוא למדעי המחשב - קריפטוגרפיה

תכנות, רקורסיה, מערכים, מחרוזות, עצים בינאריים ורשימות מקושרות

סטטיסטיקות מבחנים

רמת קושי:

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

(i) אליס מגרילה מספר ראשוני גדול $p$ (בעל ייצוג בינארי באורך $t$ ביטים) ושני מספרים אקראיים $1 < g < p$ וכן $1 < h < p$ .
(ii) בנוסף, אליס מגרילה מספר אקראי $1 < a < p$ ומחשבת $x = g^{a} \cdot h mod p$ .
(iii) אליס שולחת את $x$ ואת $p, g, h$ לבוב.
(iv) בוב מגריל מספר אקראי $1 < b < p$ ומחשב $y = g^{b} \cdot h mod p$ .
(v) בוב שולח את $y$ לאליס.
(vi) אליס מחשבת: $k_{A} = (g^{h})^{a} \cdot (y \cdot h)^{h} mod p$ , ובוב מחשב: $k_{B} = (g^{h})^{b} \cdot (x \cdot h)^{h} mod p$ .

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

1. ניתן לבצע את החישוב שאליס ובוב עושים בסיבוכיות זמן פולינומית ב-

t

.

2. מובטח שבסוף הפרוטוקול אליס ובוב מסכימים על אותו מפתח (כלומר בסוף הפרוטוקול תמיד

k_{A} = k_{B}

).

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

k_{A}

בסיבוכיות זמן פולינומית ב-

t

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2025 · סמסטר ב

★★★★★

קריפטוגרפיהסיבוכיות זמן

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

1 < g < p - 1

אליס בוחרת באקראי a בתחום $1 < a < p - 1$ , מחשבת $x = p o w (g, a, p)$ , ושולחת x לבוב.
בוב בוחר באקראי b בתחום $1 < b < p - 1$ , מחשב $y = p o w (g, b, p)$ , ושולח y לאליס.
בוב מחשב $c = p o w (x, b, p)$ , בעוד אליס מחשבת $d = p o w (y, a, p)$ . כפי שראינו בהרצאה, מתקיים $c = d$ , וערך זה הוא המפתח הסודי המשותף.

א. איב יודעת את p ו-g, שהם פומביים, ושומעת את x ו-y הודות להאזנה לתקשורת. מה מונע ממנה לשחזר את המפתח הסודי המשותף לאליס ובוב?

ב. המנהל הכללי בארגון הביון מציע להחליף את המימוש הקיים במימוש הבא:

אליס מחשבת ושולחת x כמו קודם. בוב מחשב ושולח y כמו קודם. כעת:

בוב מחשב: $c = (p o w (g, 2 b, p) \cdot x \cdot x) % p$
אליס מחשבת: $d = (p o w (g, 2 a, p) \cdot y \cdot y) % p$

האם המימוש של המנהל הכללי אכן מייצר מפתח משותף ל-Alice ו-Bob, כלומר האם

d = c

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד ב · 2018 · סמסטר ב

★★★★★

קריפטוגרפיה

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

N

.

כל החישובים נעשים מודולו

p

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

g^{a}

הכוונה היא ל-

g^{a} mod p

.

א. (6 נק') נניח

N = 3

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

g^{a}

(פעם אחת), ושולחת זאת ל-Bob ול-Carol.

כעת Alice ו-Bob חולקים את הסוד

g^{ab}

, Alice ו-Carol את הסוד

g^{a c}

, ואילו Bob ו-Carol את הסוד

g^{b c}

.

כל זוג שולח את הסוד המשותף שלו למשתמש השלישי. למשל, Alice ו-Bob שולחים (אחד מהם או שניהם, לא משנה) ל-Carol את

g^{ab}

, ובדומה גם שאר הזוגות.

וכל משתמש יכול כעת לחשב את הסוד המשותף

g^{ab c}

.

כמה פעולות modular exponentiation מבצע כל משתמש?

ב. (6 נק') תארו במילים פרוטוקול דומה, בו כל משתמש מבצע 3 פעולות modular exponentiation בלבד. ציינו אילו הודעות נשלחות בכל שלב. אפשר להיעזר באיור בדומה לאיורים לעיל.

ג. (8 נק') להלן תיאור של פרוטוקול מורחב עבור

N = 8

משתתפים. נסמן את הסוד הפרטי של משתתף

i

ב-

a_{i}

.

שלב 1: מחלקים את המשתמשים ל-2 קבוצות שוות, ושולחים את ההודעות הבאות:
קבוצה {1,2,3,4}:

1 \to 2 : g^{a_{1}}

2 \to 3 : g^{a_{1} a_{2}}

3 \to 4 : g^{a_{1} a_{2} a_{3}}

4 \to

קבוצה שניה:

g^{a_{1} a_{2} a_{3} a_{4}}

.
קבוצה {5,6,7,8}:

5 \to 6 : g^{a_{5}}

6 \to 7 : g^{a_{5} a_{6}}

7 \to 8 : g^{a_{5} a_{6} a_{7}}

8 \to

קבוצה ראשונה:

g^{a_{5} a_{6} a_{7} a_{8}}

.

שלב 2: מחלקים כל קבוצה באופן דומה וחוזרים על התהליך, כאשר בכל קבוצה ההודעה ההתחלתית היא ההודעה שנשלחה בסוף השלב הקודם מהקבוצה השנייה. למשל, משתתפים 1, 2, 3 ו-4 מחולקים שוב וחוזרים על התהליך, עם ההודעה ההתחלתית

g^{a_{5} a_{6} a_{7} a_{8}}

.

1) איזו הודעה ישלח משתתף 1 ל-2 בשלב השלישי (והאחרון)?
2) איזו פעולה יעשה משתתף 2 לאחר השלב השלישי, כדי לחשב את הסוד המשותף?
3) מהו הסוד המשותף לכל 8 המשתתפים?
4) עבור

N

משתתפים, כמה פעולות modular exponentiation מבצע כל משתתף? יש לתת תשובה במונחים של

N

, הדוקה ככל שניתן.

O (

___

)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2016 · סמסטר ב

★★★★★

קריפטוגרפיה

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

האות a תישאר a, האות c תוחלף ב-d וכן הלאה. אם כן ההודעה "abcd" תוצפן ל-"acdb".

המילון צריך כמובן לייצג מיפוי חד חד ערכי ועל מהא"ב לעצמו: כל תו ממופה לתו אחד, ואין תו שממופים אליו כמה תווים.

א. השלימו את הפונקציה הבאה encrypt, שמקבלת מחרוזת text ומילון d המייצג מיפוי כנ"ל מא"ב לעצמו (ייתכן שיש ב-text תווים שלא מופיעים במיפוי הזה). הפונקציה תחזיר את המחרוזת המוצפנת המתקבלת מ-text לאחר שתווים שלא מופיעים במילון יישארו ללא שינוי.

הפעלת המיפוי שמיוצג ב-d. תווים ב-text שלא מופיעים במילון יישארו ללא שינוי.

דוגמת הרצה:

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

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד א · 2016 · סמסטר א

★★★★★

קריפטוגרפיהמחרוזותגנרטוריםפרמוטציות

יהי

p

מספר ראשוני כלשהו, באורך

n

ביטים.

עבור שני שלמים

1 \leq a, b \leq p - 1

נאמר כי

b

הוא הופכי כפלי מודולו

p

של

a

אם

a \cdot b = 1 mod p

.

לפני זמן רב (מאוד) כשבני למד לתואר ראשון במתמטיקה, נודע לו כי לכל

1 \leq a \leq p - 1

קיים הופכי כפלי מודולו

p

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

p

של

a

נתון (

1 \leq a \leq p - 1

לכל $b = 1, 2, 3, \dots, p - 1$ :
נחשב $(a \cdot b) mod p$
אם התוצאה היא 1, נחזיר את $b$ ונסיים

א. עבור

p = 7

, מהו ההופכי הכפלי מודולו

p

של

a = 2

?

ב. מהו מספר הכפלות מודולו

p

הנדרש ע"י האלגוריתם של בני במקרה הטוב ביותר? ומהו במקרה הגרוע ביותר? בטאו את התשובה כפונקציה של

n

, תוך שימוש בסימון

O

.

מספר הכפלות במקרה הטוב ביותר:

O ()

מספר הכפלות במקרה הגרוע ביותר:

O ()

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

a^{p - 1} = 1 mod p לכל 1 \leq a \leq p - 1

לטענת אמיר, זהות זו מאפשרת למצוא הופכי כפלי מודולו

p

באופן הרבה יותר יעיל.

כיתבו ביטוי מתמטי מפורש עבור ההופכי הכפלי של

a

מודולו

p

, בהתבסס על המשפט הקטן של פרמה.

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

ה. מהו מספר הכפלות מודולו

p

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

n

, במקרה הגרוע?
כיתבו ביטוי במונחי

O (...)

ונמקו בקצרה.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד ב · 2015 · סמסטר ב

★★★★★

סיבוכיות זמןקריפטוגרפיה

לפניכם הפונקציה is_prime אשר נלמדה בהרצאה:

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

m

הוא פריק אף על פי שהוא בעצם ראשוני, בהסתברות של

(\frac{1}{4})^{100}

.

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

m

אשר יש לפרקו לגורמים — הוא יקרא לפונקציה is_prime(m, True). אם המספר אינו ראשוני הפונקציה תדפיס גם את העד (witness). כאשר דני יחלק את המספר

m

ב-witness שהודפס הוא יקבל את הגורם השני של המספר

m

וכך יפצח את הקוד. האם תוכניתו של דני תצליח לפרק מספר פריק

m > 2^{1000}

לגורמים? אם לא, נמקו.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד ב · 2012 · סמסטר ב

★★★★★

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

יהופץ וצפניה משחקים: צפניה בוחר מספר סודי

x

מתוך

X = range (2^{26})

, ויהופץ צריך לנחש אותו ע"י שאילת שאלות כן/לא, כל אחת מהצורה "נתונה קבוצה

S \subset X

, האם

x \in S

?". צפניה עונה לשאלות אולם רשאי לשקר פעם אחת. הפונקציה tzfania(S) מחזירה ערך בוליאני; תשובותיה עקביות (אין טעם לחזור על שאלה).

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

ידוע כי לכל

m \geq 2

קיים קוד Hamming עם פרמטרים

(n = 2^{m} - 1, k = 2^{m} - m - 1, d = 3)

. באפשרותכם להשתמש בפונקציה get_Hamming_code(m) שמחזירה רשימה של

2^{k}

מילות קוד, כל אחת כמחרוזת בינארית באורך

n

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמבחן לדוגמה · 2011 · סמסטר ב

★★★★★

קידודחיפושקריפטוגרפיה

נתון כרומוזום

X

המיוצג כמחרוזת באורך

n = 200000000

תווים מעל הא"ב

Σ = {A, C, G, T}

. הכרומוזום מכיל מספר לא ידוע של צמדי חזרות ארוכים (

k \geq 100

).

שלשת מספרים

(i, j, k)

תיקרא צמד חזרה אם

0 \leq i < j \leq n - k

ומתקיים

X [i : i + k] = X [j : j + k]

. צמד חזרה ייקרא מקסימלי אם הוא לא מוכל בצמד חזרה אחר:

X [i - 1] \neq = X [j - 1]

ו-

X [i + k] \neq = X [j + k]

.

*דוגמה:* ב-

X =

"ATCAAGTCAATCA" הצמדים המקסימליים מאורך

\geq 3

הם

(0, 9, 4), (1, 6, 4), (6, 10, 3)

.

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

k \geq 100

ב-

X

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

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

ג. הניחו

m

צמדי חזרות, כולם באורך

100 \leq k < 1000

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

n, m

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

אוניברסיטת תל אביבמועד ב · 2011 · סמסטר ב

★★★★★

מחרוזותתת-מחרוזתטבלאות גיבובקריפטוגרפיהסיבוכיות זמןסיבוכיות מקוםהסתברות

שאלות קריפטוגרפיה במבוא למדעי המחשב עם פתרונות

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