הצפנת אוקמוטו-אושיאמה

בקריפטוגרפיה, הצפנת אוקמוטו-אושיאמה (באנגלית: Okamoto-Uchiyama Cryptosystem) המסומנת בקיצור OU, היא מערכת הצפנת מפתח ציבורי הומומורפית שהתגלתה ב-1998 על ידי Tatsuaki Okamoto ו-Shigenori Uchiyama מחברת ניפון טלגרף אנד טלפון (NTT)^[1]. היא שונה מ-RSA ומדיפי-הלמן בכך שזאת מערכת הצפנה מוכחת כבטוחה בהנחה שפירוק לגורמים היא בעיה קשה והיא פועלת מעל חבורת אוילר $\mathbb {Z} _{n}^{*}$ כאשר $n=p^{2}q$ וכן $p$ ו- $q$ ראשוניים.

תיאור כללי

OU היא תמורה חד-כיוונית עם דלת צונחת כאשר הדלת הצונחת היא אלגוריתם יעיל לחישוב לוגריתמים בתת-חבורה ספציפית הנקראת חבורת p. החד-כיווניות שלה נובעת מבעיית פירוק לגורמים של המודולוס $n=p^{2}q$ וכן אפשר להוכיח שהטקסט המוצפן בטוח סמנטית כולו נגד יריב פסיבי. בגלל ש-OU הסתברותית הטקסט המוצפן נראה אקראי, כי כל טקסט קריא יכול להיות מוצפן עם אותו מפתח באופן שונה בכל פעם. הביטחון הסמנטי מסתמך על הקושי שבהבחנה בין $E(0,r)=h^{r}{\text{ mod }}n$ לבין $E(1,r')=gh^{r'}{\text{ mod }}n$ כאשר $r$ ו- $r'$ אקראיים ובלתי תלויים ב- $\mathbb {Z} _{n}$ . בעיה זו נחשבת לבעיה קשה והיא שקולה לבעיית השארית הריבועית וכן שארית מסדר גבוה יותר שנחשבות לבעיות קשות. שיטת OU נחשבת ליעילה יותר בהשוואה ל-RSA להצפנה של ערכים קטנים כמו מפתח הצפנה והיא הומומורפית בגלל התכונה הבאה:

$E(m_{0},r_{0})E(m_{1},r_{1}){\text{ mod }}n=E(m_{0}+m_{1},r_{3})$ אם $m_{0}+m_{1}<p$ .

תכונה זו שימושית במקומות בהם נדרשת הצפנה אנונימית כמו בהצבעה דיגיטלית ובמטבע דיגיטלי. החסרונות של שיטת OU הם: התנפחות הטקסט המוצפן וכן העובדה שהיא אינה בטוחה נגד יריב אקטיבי לפי מודל התקפת מוצפן-נבחר. אפשר ליישם טכניקת ריפוד דומה לזו שנעשתה ב-RSA כדי לקבל ביטחון סמנטי במסגרת מודל אורקל אקראי. כמו כן שיטה זו חשילה כי זה נובע מהתכונה הייחודית שלה. לא ידוע אם הקושי שבפירוק $n=p^{2}q$ שונה מהקושי שבפירוק $n=pq$ לכן $n$ יכול להיות באורך זהה בשני המקרים (למשל 2046 סיביות כאשר כל ראשוני באורך 682 סיביות).

פונקציה לוגריתמית

נתונה החבורה $\mathbb {Z} _{n}$ (כאשר $n=p^{2}q$ וכן $p$ ו- $q$ ראשוניים), הפונקציה הלוגריתמית $L$ מוגדרת מעל $p$ -סילו - תת-חבורה של החבורה הכפלית $\mathbb {Z} _{p^{2}}^{*}$ . אם נתון ראשוני $p$ הקבוצה:

\Gamma =\{x\in \mathbb {Z} _{p^{2}}^{*}|x\equiv 1{\text{ (mod }}p)\}

.

היא חבורה ציקלית מסדר $p(p-1)$ לכן $\#\Gamma =p$ . הפונקציה $L$ עבור $x\in \Gamma$ קלה לחישוב והיא:

L(x)={\frac {x-1}{p}}

.

והיא מוגדרת היטב. הפונקציה $L(x)$ נקראת "פונקציה לוגריתמית" של $\Gamma$ והביטוי שקול ל- $\log(x)$ מעל $\mathbb {Z} _{p^{2}}^{*}$ מודולו $p$ . היא הומומורפית ביחס לפעולות הכפל והחיבור כי:

\forall x,y\in \Gamma \ \ \log(xy{\text{ mod }}p^{2})=\log(x)+\log(y){\text{ mod }}p

ולכן מתקיים:

\forall g\in \Gamma ,m\in \mathbb {Z} _{p}\ \ \log(g^{m}{\text{ mod }}p^{2})=m\cdot \log(g){\text{ mod }}p

ההוכחה במאמר המקורי.

הצפנה ופענוח

הכנה

יהי $k$ פרמטר ביטחון (למשל $k=682$ ), בוחרים שני ראשוניים אקראיים $p$ ו- $q$ כאשר $|p|=|q|=k$ ומחשבים את $n=p^{2}q$ . בוחרים אלמנט אקראי $g\in _{R}\mathbb {Z} _{n}^{*}$ כך שהסדר של $g_{p}=g^{p-1}{\text{ mod }}p^{2}$ הוא $p$ . לא קשה למצוא איבר כזה כי ${\text{gcd}}(p,q-1)=1$ וכן ${\text{gcd}}(q,p-1)=1$ כאשר gcd היא פונקציית מחלק משותף מקסימלי (לכן כל מה שצריך זה לוודא ש- $g_{p}\neq 1$ ). מחשבים את $h=g^{n}{\text{ mod }}n$ .

המפתח הציבורי הוא: $(n,g,h)$ . המפתח הפרטי הוא: $(p,q)$ .

$h$ ניתן לחישוב בכל שלב מתוך $g$ ו- $n$ והוא נועד רק להקל על החישובים בצד המצפין, אין חובה לשלוח אותו.

הצפנה

בהינתן טקסט גלוי $m$ באורך $k-1$ סיביות לכל היותר. בוחרים שלם אקראי $r\in _{R}\mathbb {Z} _{n}$ ומחשבים את:

c=g^{m}h^{r}{\text{ mod }}n

.

פענוח

תחילה מחשבים את $c_{p}=c^{p-1}{\text{ mod }}p^{2}$ ואז הטקסט הגלוי מתקבל על ידי

m={\frac {L(c_{p})}{L(g_{p})}}{\text{ mod }}p

דרך אחרת להציג זאת (הכפלה בהופכי כפלי במקום חילוק):

m=\log(c_{p})\cdot \log(g_{p})^{-1}{\text{ mod }}p

זה נכון כי לפי חוקי הלוגריתמים $\log(x)/\log(g)$ הוא במובן מסוים הלוגריתם של $x$ בבסיס $g$ , לפי זה אם נתון:

(g^{m}h^{r})^{p-1}\equiv (g^{m}g^{nr})^{p-1}\equiv (g^{p-1})^{m}{\text{ (mod }}p^{2})

כל מה שצריך כדי לחלץ את $m$ זה לקחת לוגריתם בבסיס $g^{p-1}$ . את זה אפשר לעשות על ידי $\textstyle m={\frac {\log((g^{p-1})^{m})}{\log(g^{p-1})}}$ מודולו $p$ .

ביטחון

יהי ${\mathcal {G}}_{1}$ מייצר ${\mathcal {G}}_{1}(1^{k})\rightarrow n,n=p^{2}q,|p|=|q|=k$ כאשר $p$ ו- $q$ ראשוניים. בעיית הפירוק בהינתן $(n,k)$ למצוא את $(p,q)$ קשה אם עבור כל אלגוריתם פולינומי הסתברותי ${\mathcal {A}}$ ועבור כל קבוע $c$ עם $k$ גדול מספיק מתקיים:

\Pr[{\mathcal {A}}(1^{k},n)=(p,q)]<1/k^{c}

.

כמו כן בהינתן מייצר ${\mathcal {G}}_{2}(1^{k})\rightarrow (n,g,c)$ ו- $(n,g,k)$ מפתח ציבורי, $c$ הטקסט המוצפן, היפוך הפונקציה קשה אם עבור כל אלגוריתם פולינומי הסתברותי ${\mathcal {A}}$ ועבור כל קבוע $c$ עם $k$ גדול מספיק מתקיים:

\Pr[{\mathcal {A}}(1^{k},n,g,c)=m]<1/k^{c}

.

קיימת הוכחה ששתי הבעיות המתוארות שקולות. אם מצליחים להפוך את פונקציית ההצפנה אז אפשר לפרק את $n$ לגורמים. בכך מוכיחים שההצפנה בטוחה בהנחה שבעיית פירוק לגורמים קשה. בדומה לבעיית השארית הריבועית, מסתמכים על העובדה שקשה להכריע האם איבר $x\in \mathbb {Z} _{n}^{*}$ הוא בתת-חבורה מסדר $p$ ומזה נובע שהטקסט המוצפן כולו בטוח סמנטית.

דוגמה במספרים קטנים

נניח שנבחרו הפרמטרים הבאים: $p=107,q=89,n=p^{2}q=1018961$ .

אם $g=23$ אז $g_{p}=23^{106}{\text{ mod }}11449=5030$ וכן $h=23^{1018961}{\text{ mod }}1018961=19003$ .

אם המסר להצפנה הוא $m=100$ ו- $r=9$ אז מתקבל $c=g^{m}h^{r}=46063\cdot 764299\equiv 802287$ מודולו $1018961$ .

לפענוח קודם מחשבים את: $c_{p}=802287^{106}{\text{ mod }}11449\equiv 10594$ .

הלוגריתמים של $c_{p}$ ושל $g_{p}$ (מודולו $p$ ) הם: $\log(10594)=10593/107=99$ וכן $\log(5030)=5029/107=47$

ואז $m=\log(10594)\cdot \log(5030)^{-1}=99\cdot 47^{-1}{\text{ mod }}107\equiv 99\cdot 41{\text{ mod }}107=100$ .

שיפורים

השלב הראשון בפענוח דורש $O(k^{3})$ פעולות על סיביות בגלל העלאה בחזקת $p-1$ . קורון נקש ופלייר הציעו לייעל את שיטת OU כך שסיבוכיותה תהיה $O(k^{2})$ מבלי לאבד את השקילות לבעיית הפירוק^[2]. הם הציעו להשתמש בראשוני $p$ כך של- $p-1$ יש גורם ראשוני גדול $t$ (באורך 160 סיביות לפחות), כלומר $p=tu+1$ . כמו בגרסה המקורית, בוחרים שלם $g<n$ ומחשבים את $g_{p}=g^{p-1}{\text{ mod }}p^{2}$ כך שהסדר שלו הוא $p$ . מחשבים את $G=g^{u}{\text{ mod }}n$ , מגרילים את $h$ ומחשבים את $H=h^{nu}{\text{ mod }}n$ . השלישייה $(n,G,H)$ היא המפתח הציבורי ואילו המפתח הפרטי הוא $(p,q)$ .

להצפנה בוחרים שלם אקראי $r<n$ ומחשבים את $c=G^{m}H^{r}{\text{ mod }}n$ ואילו לפענוח מחשבים את:

c_{p}=c^{t}{\text{ mod }}p^{2}=g^{m(p-1)}h^{nr(p-1)}=g_{p}^{m}{\text{ mod }}p^{2}

m=\log(c_{p})\cdot \log(g_{p})^{-1}{\text{ mod }}p

הסיבוכיות השתפרה כי $t$ קטן מ- $p$ .

EPOC

EPOC קיצור של Efficient Probabilistic Public Key Encryption היא מערכת הצפנה הסתברותית שפותחה ב-1999 על ידי Okamoto, Uchiyama ו-Fujisaki מ-NTT והוצעה לתקן 1363a-2004 IEEE. היא מבוססת על פונקציית OU המתוארת^[3]^[4] והיא הוכחה בטוחה סמנטית נגד תקיפת מוצפן-נבחר במסגרת מודל אורקל אקראי, כלומר היא פועלת בשילוב עם פונקציית גיבוב. הגרסה הראשונה EPOC-1 נועדה רק לשיתוף מפתח. גרסת EPOC-2 משלבת גם פד חד-פעמי/צופן סימטרי. גרסת EPOC-3 משתמשת בשתי פונקציות גיבוב $H$ ו- $G$ והיא מבצעת הצפנה מאומתת כדלהלן. בהינתן פרמטר ביטחון $k$ של פונקציית הצפנה אסימטרית ${\text{ASYM}}$ כמו זו המתוארת לעיל ופונקציית הצפנה סימטרית ${\text{SYM}}$ כמו צופן זרם או צופן בלוקים. מכינים מפתח פרטי $sk$ ומפתח ציבורי $pk$ של פונקציית ההצפנה האסימטרית ומבצעים:

הצפנה	פענוח
$\sigma \leftarrow _{R}\{0,1\}^{k}$ $r_{1}=H(\sigma ,m)$ $r_{2}=G(\sigma )$ $c_{1}={\text{ENC}}\_{\text{ASYM}}_{pk}(\sigma ,r_{1})$ $c_{2}={\text{ENC}}\_{\text{SYM}}_{r_{2}}(m)$ ‎ ${\text{return }}(c_{1},c_{2})$	$\sigma ={\text{DEC}}\_{\text{ASYM}}_{sk}(c_{1})$ $r_{2}=G(\sigma )$ $m={\text{DEC}}\_{\text{SYM}}_{r_{2}}(c_{2})$ $r_{1}=H(\sigma ,m)$ ${\text{If }}c_{1}={\text{ENC}}\_{\text{ASYM}}_{pk}(\sigma ,r_{1}){\text{ then:}}$ $\ \ \ \ {\text{return }}m$ ${\text{else return }}\bot$