אלגוריתם הצפנה RSA

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

אלגוריתם הצפנת מפתח ציבורי:

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

מפתח ציבורי מפתח פרטי

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

אלגוריתם המפתח הציבורי פועל באופן הבא:

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

אלגוריתם הצפנת RSA:

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

אלגוריתם RSA משתמש בהליך הבא כדי ליצור מפתחות ציבוריים ופרטיים:

בחר שני מספרים ראשוניים גדולים, p ו ש .
הכפל את המספרים הללו כדי למצוא n = p x q, איפה נ נקרא מודול להצפנה ופענוח.
בחר מספר זה פחות מ נ , כך ש-n הוא ראשוני יחסית ל (p - 1) x (q -1). זה אומר ש זה ו (p - 1) x (q - 1) אין גורם משותף מלבד 1. בחר 'e' כך ש-1 gcd (e,d(n)) =1
אם n = p x q, אז המפתח הציבורי הוא . הודעת טקסט רגיל M מוצפן באמצעות מפתח ציבורי. כדי למצוא טקסט צופן מהטקסט הפשוט נעשה שימוש בנוסחה הבאה כדי לקבל טקסט צופן C.
C = m^זהנגד נ
כאן , M חייב להיות פחות מ נ . הודעה גדולה יותר (>n) מטופלת כשרשור של הודעות, שכל אחת מהן מוצפנת בנפרד.
כדי לקבוע את המפתח הפרטי, אנו משתמשים בנוסחה הבאה כדי לחשב את ה-d כך:
ד_זהmod {(p - 1) x (q - 1)} = 1
אוֹ
ד_זהmod φ (n) = 1
המפתח הפרטי הוא . הודעת טקסט מוצפנת ג מפוענח באמצעות מפתח פרטי. לחישוב טקסט רגיל M מהצופן c הנוסחה הבאה משמשת כדי לקבל טקסט רגיל m.
m = c^דנגד נ

בואו ניקח דוגמה לאלגוריתם הצפנת RSA:

דוגמה 1:

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

כתב כתיבה עבור כל אחד

הֶסבֵּר:

שלב 1: בחר שני מספרים ראשוניים גדולים, p, ו ש .

p = 7

q = 11

שלב 2: הכפל את המספרים הללו כדי למצוא n = p x q, איפה נ נקרא מודול להצפנה ופענוח.

ראשית, אנו מחשבים

n = p x q

n = 7 x 11

n = 77

שלב 3: בחר מספר זה פחות ש נ , כך ש-n הוא ראשוני יחסית ל (p - 1) x (q -1). זה אומר ש זה ו (p - 1) x (q - 1) אין גורם משותף מלבד 1. בחר 'e' כך ש-1

שנית, אנחנו מחשבים

φ (n) = (p - 1) x (q-1)

φ (n) = (7 - 1) x (11 - 1)

φ (n) = 6 x 10

φ (n) = 60

הבה נבחר כעת ראשוני e יחסי של 60 כ-7.

לפיכך המפתח הציבורי הוא = (7, 77)

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

כדי למצוא טקסט צופן מהטקסט הפשוט נעשה שימוש בנוסחה הבאה כדי לקבל טקסט צופן C.

C = m^זהנגד נ

C = 9⁷נגד 77

C = 37

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

ד_זהmod {(p - 1) x (q - 1)} = 1

7d mod 60 = 1, מה שנותן d = 43

המפתח הפרטי הוא = (43, 77)

שלב 6: הודעת טקסט מוצפנת ג מפוענח באמצעות מפתח פרטי. לחישוב טקסט רגיל M מהצופן c הנוסחה הבאה משמשת כדי לקבל טקסט רגיל m.

יצירת רשימה ב-java

m = c^דנגד נ

m = 37⁴³נגד 77

m = 9

בדוגמה זו, טקסט רגיל = 9 וטקסט הצופן = 37

דוגמה 2:

במערכת קריפטו RSA, A מסוים משתמש בשני מספרים ראשוניים, 13 ו-17, כדי ליצור את המפתחות הציבוריים והפרטיים. אם הציבור של A הוא 35. אז המפתח הפרטי של A הוא ……………?.

הֶסבֵּר:

שלב 1: בשלב הראשון, בחר שני מספרים ראשוניים גדולים, ע ו ש .

p = 13

q = 17

שלב 2: הכפל את המספרים הללו כדי למצוא n = p x q, איפה נ נקרא מודול להצפנה ופענוח.

ראשית, אנו מחשבים

n = p x q

n = 13 x 17

n = 221

שנית, אנחנו מחשבים

φ (n) = (p - 1) x (q-1)

φ (n) = (13 - 1) x (17 - 1)

φ (n) = 12 x 16

φ (n) = 192

g.c.d (35, 192) = 1

שלב 3: כדי לקבוע את המפתח הפרטי, אנו משתמשים בנוסחה הבאה כדי לחשב את ה-d כך:

חשב את d = d_זהmod φ (n) = 1

d = d x 35 mod 192 = 1

d = (1 + k.φ (n))/e [תן k =0, 1, 2, 3………………]

פיט דיווידסון

שים k = 0

d = (1 + 0 x 192)/35

d = 1/35

שים k = 1

d = (1 + 1 x 192)/35

ד = 193/35

שים k = 2

d = (1 + 2 x 192)/35

d = 385/35

d = 11

המפתח הפרטי הוא = (11, 221)

לפיכך, מפתח פרטי כלומר d = 11

דוגמה 3:

מערכת קריפטו RSA משתמשת בשני מספרים ראשוניים 3 ו-13 כדי ליצור את המפתח הציבורי= 3 והמפתח הפרטי = 7. מה הערך של טקסט צופן עבור טקסט רגיל?

הֶסבֵּר:

שלב 1: בשלב הראשון, בחר שני מספרים ראשוניים גדולים, ע ו ש .

p = 3

q = 13

שלב 2: הכפל את המספרים הללו כדי למצוא n = p x q, איפה נ נקרא מודול להצפנה ופענוח.

ראשית, אנו מחשבים

n = p x q

n = 3 x 13

n = 39

שלב 3: אם n = p x q, אז המפתח הציבורי הוא . הודעת טקסט רגיל M מוצפן באמצעות מפתח ציבורי. לפיכך המפתח הציבורי הוא = (3, 39).

כדי למצוא טקסט צופן מהטקסט הפשוט נעשה שימוש בנוסחה הבאה כדי לקבל טקסט צופן C.

C = m^זהנגד נ

C = 5³מול 39

C = 125 לעומת 39

C = 8

לפיכך, טקסט הצופן שנוצר מטקסט רגיל, C = 8.

דוגמה 4:

מערכת הצפנה RSA משתמשת בשני מספרים ראשוניים, 3 ו-11, כדי ליצור מפתח פרטי = 7. מה הערך של טקסט צופן עבור טקסט רגיל 5 באמצעות אלגוריתם ההצפנה RSA המפתח הציבורי?

הֶסבֵּר:

שלב 1: בשלב הראשון, בחר שני מספרים ראשוניים גדולים, ע ו ש .

אריה לעומת נמר

p = 3

q = 11

שלב 2: הכפל את המספרים הללו כדי למצוא n = p x q, איפה נ נקרא מודול להצפנה ופענוח.

ראשית, אנו מחשבים

n = p x q

n = 3 x 11

n = 33

שנית, אנחנו מחשבים

φ (n) = (p - 1) x (q-1)

φ (n) = (3 - 1) x (11 - 1)

אלגוריתם dfs

φ (n) = 2 x 10

φ (n) = 20

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

חשב e x d = 1 mod φ (n)

e x 7 = 1 נגד 20

e x 7 = 1 מול 20

e = (1 + k. φ (n))/ ד [תן k =0, 1, 2, 3………………]

שים k = 0

e = (1 + 0 x 20) / 7

e = 1/7

שים k = 1

e = (1 + 1 x 20) / 7

e = 21/7

e = 3

המפתח הציבורי הוא = (3, 33)

לפיכך, מפתח ציבורי כלומר e = 3