הצפנת פליאיי

הצפנת פֵּלִיאֵי (באנגלית: Paillier Encryption)^[1] היא סכימת הצפנה אסימטרית הסתברותית הומומורפית וחתימה דיגיטלית שהומצאה ב-1999 על ידי פסקל פליאיי (Pascal Paillier) לשעבר מחברת GEMPLUS לוקסמבורג. הצפנת פליאיי הומצאה בהשראת סכימות הצפנה הסתברותית כמו בלום גולדווסר והיא מבוססת על פונקציה חד-כיוונית עם דלת צונחת שנגזרת מבעיה בתורת המספרים הנקראת בעיית השאריות הפריקות (Composite Residuosity Class Problem) מודולו ${\displaystyle \textstyle n^{2}}$ כאשר ${\displaystyle n}$ מכונה "מספר RSA" (כפולה של שני ראשוניים שונים שווים בגודלם בקירוב).

רקע מתמטי

הבסיס התאורטי של המערכת הוא, בהינתן שלם ${\displaystyle n=pq}$ כאשר ${\displaystyle p}$ ו-${\displaystyle q}$ ראשוניים גדולים, שווים באורכם בקירוב והחבורה ${\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{n}^{*}\simeq \mathbb {Z} _{n^{2}}^{*}}$, השלם ${\displaystyle z}$ ייקרא שארית ${\displaystyle n}$-ית (ממעלה ${\displaystyle n}$) מודולו ${\displaystyle n^{2}}$ אם קיים שלם ${\displaystyle y\in \mathbb {Z} _{n^{2}}^{*}}$ המקיים

${\displaystyle z=y^{n}{\text{ mod }}n^{2}}$.

קבוצת השאריות ה-${\displaystyle n}$-יות היא תת-חבורה כפלית ${\displaystyle \mathbb {Z} _{n^{2}}^{*}}$. לכל ${\displaystyle z}$ כזה קיימים בדיוק ${\displaystyle n}$ שורשים ממעלה ${\displaystyle n}$. בעיית ההכרעה האם שלם נתון הוא שארית ${\displaystyle n}$-ית או לא, המסומנת בקיצור ${\displaystyle {\text{CR}}[n]}$ (קיצור של Composite Residuosity) נחשבת לבעיה קשה ולא ידוע על אלגוריתם יעיל שיכול לבצעה בזמן פולינומי. סדר החבורה ${\displaystyle \mathbb {Z} _{n^{2}}^{*}}$ הוא ${\displaystyle n\phi (n)}$ כאשר ${\displaystyle \phi (n)}$ היא פונקציית אוילר של ${\displaystyle n}$.

הפונקציה ${\displaystyle {\mathcal {E}}_{g}(x,y)}$ המוגדרת על ידי

${\displaystyle (x,y)\mapsto g^{x}y^{n}{\text{ mod }}n^{2}}$

עבור ${\displaystyle x\in \mathbb {Z} _{n}}$ ו-${\displaystyle y\in \mathbb {Z} _{n}^{*}}$ היא פונקציה חד-חד-ערכית ועל מעל החבורה ${\displaystyle \mathbb {Z} _{n^{2}}^{*}}$ ביחס לבסיס ${\displaystyle g\in {\mathcal {B}}}$ נתון. ${\displaystyle g}$ הוא אלמנט מסדר ${\displaystyle \alpha \cdot n}$ עבור מחלק ${\displaystyle \alpha }$ כלשהו של ${\displaystyle \phi }$. הקבוצה ${\displaystyle {\mathcal {B}}}$ היא קבוצת כל האלמנטים מסדר ${\displaystyle n\alpha }$ עבור ${\displaystyle \alpha =1,...,\phi }$ (לדוגמה אפשר לבחור ${\displaystyle g=n+1}$ כש-${\displaystyle \alpha =1}$).

אפשר לראות שהפונקציה ${\displaystyle w={\mathcal {E}}_{g}(x,y)}$ הפיכה. כדי להפוך את הפונקציה מגדירים את ${\displaystyle L(u)=(u-1)/n}$ שהיא פונקציה מעל תת-חבורה כפלית של השלמים מודולו ${\displaystyle n^{2}}$ המקיימים ${\displaystyle u\equiv 1{\text{ mod }}n}$. שחזור הערכים ${\displaystyle x,y}$ מתוך ${\displaystyle w={\mathcal {E}}_{g}(x,y)}$ מתבצע על ידי

${\displaystyle x=\left({\frac {L(w^{\phi }{\text{ mod }}n^{2})}{L(g^{\phi }{\text{ mod }}n^{2})}}\right){\text{ mod }}n}$

${\displaystyle y=(wg^{-x})^{1/n}{\text{ mod }}n}$

במקום ${\displaystyle \phi }$ של ${\displaystyle n}$ אפשר לעבוד עם פונקציית קרמייקל שהיא ${\displaystyle \lambda (n)={\text{lcm}}(p-1,q-1)}$. זהו האקספוננט של חבורת אוילר ו-${\displaystyle {\text{lcm}}}$ היא כפולה משותפת מינימלית. שימו לב שלפי משפט קרמייקל עבור כל אלמנט ${\displaystyle w\in \mathbb {Z} _{n^{2}}^{*}}$ מתקיים ${\displaystyle w^{\lambda }\equiv 1{\text{ mod }}n}$ וכן ${\displaystyle w^{n\lambda }\equiv 1{\text{ mod }}n^{2}}$. בהמשך ייעשה שימוש ב-${\displaystyle \lambda }$ בכל המקומות בהן הופיעה פונקציית אוילר.

דלת המלכודת היא הגורמים הראשוניים או ${\displaystyle \lambda }$. כאשר הגורמים הראשוניים של ${\displaystyle n}$ לא ידועים שחזור ${\displaystyle x}$ מתוך ${\displaystyle {\mathcal {E}}_{g}(x,y)}$ ואפילו להכריע האם ${\displaystyle x=0}$ ללא ${\displaystyle \lambda }$ נחשבים לבעיה קשה תחת המודל הסטנדרטי של סיבוכיות חישובית, בהנחה שפירוק לגורמים של ${\displaystyle n}$ אינו מעשי. האחרונה נקראת בעיית הכרעה של השאריות הפריקות ומסומנת בקיצור DCRA.

סכימות הצפנה וחתימה דיגיטלית

על בסיס הרעיון האמור הצפנת פליאיי פועלת כדלהלן. יהי ${\displaystyle n=pq}$ ויהי ${\displaystyle g\in {\mathcal {B}}}$, אפשר למצוא ערך כזה על ידי בדיקה אם

${\displaystyle {\text{gcd}}(L(g^{\lambda }{\text{ mod }}n^{2}),n)=1}$. הפונקציה ${\displaystyle {\text{gcd}}}$ מייצגת מחלק משותף מקסימלי.

הערכים ${\displaystyle n}$ ו-${\displaystyle g}$ יהיו מפתחות ציבוריים ואילו ${\displaystyle p}$ ו-${\displaystyle q}$ יהיו המפתחות הפרטיים (במקום המספרים הראשוניים אפשר לשמור את ${\displaystyle \lambda }$). בהינתן מסר ${\displaystyle m}$ הנמוך מ-${\displaystyle n}$ להצפנה בוחרים שלם אקראי ${\displaystyle r<n}$ ומבצעים:

${\displaystyle c=g^{m}\cdot r^{n}{\text{ mod }}n^{2}}$

לפענוח:

${\displaystyle m={\frac {L(c^{\lambda }{\text{ mod }}n^{2})}{L(g^{\lambda }{\text{ mod }}n^{2})}}{\text{ mod }}n}$

או ${\displaystyle L(c^{\lambda }{\text{ mod }}n^{2})\cdot L(g^{\lambda }{\text{ mod }}n^{2})^{-1}}$ מודולו ${\displaystyle n}$. הסכימה נחשבת הסתברותית בגלל ${\displaystyle r}$ והיא בטוחה סמנטית כנגד יריב פסיבי, בהנחה שבעיית ${\displaystyle {\text{CR}}[n]}$ היא בעיה קשה ושקשה לפרק את ${\displaystyle n}$ לגורמים. סיבוכיות ההצפנה היא מסדר גודל של ${\displaystyle O(|n|^{3})}$ בקירוב.

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

לצורך המחשה הראשוניים יהיו ${\displaystyle q=331}$, ${\displaystyle p=149}$. לכן ${\displaystyle n=49319}$ ו-${\displaystyle n^{2}=243236376}$. הערך ${\displaystyle \lambda ={\text{lcm}}(148,330)=24420}$. הבסיס נקבע ל-${\displaystyle g=n+1=49320}$.

מפתח ציבורי: ${\displaystyle 49319}$.

מפתח פרטי: ${\displaystyle 24420}$.

לצורך הצפנת המסר ${\displaystyle m=12345}$ בוחרים מספר אקראי נניח ${\displaystyle r=47026}$ ואז מחשבים את ${\displaystyle c=49320^{12345}\cdot 47026^{49319}{\text{ mod }}2432363761=159515031}$.

הטקסט המוצפן הוא אם כן ${\displaystyle c=159515031}$.

לפענוח תחילה מחשבים את ${\displaystyle L(49320^{12345}{\text{ mod }}2432363761)=27172}$ וכן ${\displaystyle L(47026^{49319}{\text{ mod }}2432363761)=24420}$.

ההופכי הכפלי של ${\displaystyle 24420}$ מודולו ${\displaystyle 49319}$ הוא ${\displaystyle 27388}$ לכן ${\displaystyle m=27172\cdot 27388{\text{ mod }}49319=12345}$.

פרמוטציה חד-כיוונית עם דלת מלכודת

להלן סכימה לא הסתברותית המבוססת חלקית על RSA שנקראת פרמוטציה חד כיוונית עם דלת מלכודת כאשר דלת המלכודת היא ${\displaystyle \lambda }$. והיא מסתמכת על בעיית ${\displaystyle {\text{CR}}[n]}$ בהנחה שפירוק לגורמים של ${\displaystyle n}$ היא בעיה קשה. למרות התלות ב-RSA הסכימה ראויה לציון בשל העובדה שפרמוטציות חד כיווניות עם דלת מלכודת (דוגמת RSA ורבין) הן אובייקטים נדירים וחשובים בקריפטוגרפיה מודרנית.

להצפנה:

תחילה מפצלים את המסר המיועד להצפנה ${\displaystyle m}$ בדרך הפיכה כלשהי לשני חלקים ${\displaystyle m_{1},m_{2}}$. למשל ${\displaystyle m=m_{1}+nm_{2}}$.

מחשבים את ${\displaystyle c=g^{m_{1}}m_{2}^{n}{\text{ mod }}n^{2}}$

לפענוח:

תחילה ${\displaystyle m_{1}={\frac {L(c^{\lambda }{\text{ mod }}n^{2})}{L(g^{\lambda }{\text{ mod }}n^{2})}}}$

מחשבים את ערך הביניים ${\displaystyle c'=cg^{-m_{1}}{\text{ mod }}n}$

${\displaystyle m_{2}=(c')^{n^{-1}{\text{ mod }}\lambda }{\text{ mod }}n}$

ואז המסר הוא ${\displaystyle m=m_{1}+nm_{2}}$.

אפשר להשתמש בכל תמורה פומבית מוסכמת שממפה את ${\displaystyle m}$ לערכים ${\displaystyle m_{1},m_{2}}$. יש לשים לב שהסכימה הזו אינה הסתברותית, כלומר אינה מערבת שימוש במספר אקראי.

חתימה דיגיטלית

לצורך חתימה דיגיטלית תהי ${\displaystyle h:\mathbb {N} \rightarrow \{0,1\}^{k}}$ פונקציית גיבוב קריפטוגרפית של המסר שתסומן בקיצור ${\displaystyle h(m)}$. עבור המסר ${\displaystyle m}$ החותם מחשב את החתימה ${\displaystyle (s_{1},s_{2})}$ כדלהלן:

${\displaystyle s_{1}={\frac {L(h(m)^{\lambda }{\text{ mod }}n^{2})}{L(g^{\lambda }{\text{ mod }}n^{2})}}{\text{ mod }}n}$

${\displaystyle s_{2}=(h(m)g^{-s_{1}})^{1/n{\text{ mod }}\lambda }{\text{ mod }}n}$

מקבל החתימה יכול לוודא את תקפותה על ידי הבדיקה שמתקיים

${\displaystyle h(m)=g^{s_{1}}s_{2}^{n}{\text{ mod }}n^{2}}$

הצפנה מהירה

סכימות כמו RSA סובלות מחסרון בכך שהפענוח דורש זמן ואינו יעיל במונחי מחשוב. מסיבה זו מערכת הצפנה אסימטרית תהיה אטרקטיבית אם הפענוח יהיה מסדר גודל כמעט ריבועי ביחס ל-${\displaystyle n}$. להלן גרסה שונה מעט שבה סיבוכיות הפענוח היא בסדר גודל של ${\displaystyle O(|n|^{2+\epsilon })}$ עבור ${\displaystyle \epsilon >0}$ קטן כלשהו. הרעיון הוא להגביל את מרחב הטקסט המוצפן ${\displaystyle \mathbb {Z} _{n^{2}}^{*}}$ לתת קבוצה ${\displaystyle <g>}$ מסדר נמוך יותר. מסיבות של ביטחון ${\displaystyle \lambda }$ צריך להיות כפולה של ראשוני גדול. בהינתן הבסיס ${\displaystyle g\in {\mathcal {B}}_{\alpha }}$ עבור ${\displaystyle 1\leq \alpha \leq \lambda }$ כלשהו, הסכימה היא כדלהלן.

הצפנה:

בוחרים אלמנט אקראי ${\displaystyle r}$ הנמוך מ-${\displaystyle n}$.

מחשבים את ${\displaystyle c=g^{m+rn}{\text{ mod }}n^{2}}$

פענוח:

${\displaystyle m={\frac {L(c^{\alpha }{\text{ mod }}n^{2})}{L(g^{\alpha }{\text{ mod }}n^{2})}}{\text{ mod }}n}$

הפעם דלת המלכודת מסתמכת על ידיעת ${\displaystyle \alpha }$ כמפתח סודי במקום ${\displaystyle \lambda }$. צוואר הבקבוק בפעולת הפענוח הוא הפעולה ${\displaystyle c^{\alpha }{\text{ mod }}n^{2}}$ שסיבוכיותה היא בסדר גודל ${\displaystyle O(|n|^{2}|\alpha |)}$ בלבד. אם ${\displaystyle g}$ נבחר באופן כזה ש-${\displaystyle |\alpha |=\Omega (|n|^{\epsilon })}$ אז כל תהליך הפענוח יתבצע עם ${\displaystyle O(|n|^{2+\epsilon })}$ פעולות בסיביות. זהו מאפיין חשוב בהשוואה למערכת אסימטריות אחרות. אולם יש לשים לב שבמקרה זה המערכת לא מסתמכת על בעיית ${\displaystyle {\text{CR}}[n]}$ כיוון שכעת ידוע שהטקסט המוצפן שייך לקבוצה ${\displaystyle <g>}$. הבעיה האחרונה, דהיינו לחשב את ${\displaystyle x,y}$ בהינתן ${\displaystyle w\in <g>}$ נקראת בעיית הלוגריתם הבדיד 'חלקית' וגם היא משוערת כבעיה קשה.

ביטחון

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

יעילות

לפי ההמלצות המקובלות הראשוניים ${\displaystyle p}$ ו-${\displaystyle q}$ צריכים להיבחר באופן שיהיה קשה לפרק את ${\displaystyle n}$ לגורמים. הבסיס ${\displaystyle g}$ יכול להיבחר באקראי (בגרסה המהירה יידרש טיפול שונה למשל להעלות אלמנט בחזקת ${\displaystyle \lambda /\alpha }$). כדי לשפר ביצועים אפשר לאמץ את שיטת CRT כמו ב-RSA, כלומר כל החישובים יתבצעו מודולו ${\displaystyle p^{2}}$ ו-${\displaystyle q^{2}}$ בהתאמה והתוצאה הסופית תהיה חישוב מערכת המשוואות המודולריות המתקבלת באמצעות משפט השאריות הסיני שהוא זניח יחסית לפעולה של העלאה בחזקה מודולרית. אם בוחרים ${\displaystyle g}$ קטן (כמו ${\displaystyle g=2}$) כל עוד הוא מקיים את ההגדרות של הסכימה, יתקבל שיפור נוסף בביצועים בסדר גודל של ${\displaystyle 1/3}$. יתרה מזו ${\displaystyle g}$ יכול להיות קבוע מה שמאפשר חישוב מוקדם כדי להאיץ ביצועים. בכללות כל הערכים הקבועים וכן חישוב ${\displaystyle r^{n}}$ או ${\displaystyle g^{nr}}$ יכולים להתבצע מראש. בפענוח חישוב הפונקציה ${\displaystyle L(u)=(u-1)/n}$ ניתן לביצוע במחיר פעולת כפל אחת מודולו ${\displaystyle 2^{|n|}}$ על ידי חישוב מוקדם של הקבוע ${\displaystyle n^{-1}{\text{ mod }}2^{|n|}}$. הקבועים ${\displaystyle L(g^{\lambda }{\text{ mod }}n^{2})^{-1}{\text{ mod }}n}$ או ${\displaystyle L(g^{\alpha }{\text{ mod }}n^{2})^{-1}{\text{ mod }}n}$ בגרסה המהירה ניתנים לחישוב מראש.

כדי לנצל את משפט השאריות הסיני (CRT) לשיפור ביצועים, יש להגדיר את הפונקציות ${\displaystyle L_{p}}$ ו-${\displaystyle L_{q}}$ כדלהלן: ${\displaystyle L_{p}(u)=(u-1)/p}$ וכן ${\displaystyle L_{q}(u)=(u-1)/q}$ בהתאמה. פענוח יתבצע כעת עם הקבועים הבאים אותם מחשבים מראש:

${\displaystyle h_{p}=L_{p}(g^{p-1}{\text{ mod }}p^{2})^{-1}{\text{ mod }}p}$

${\displaystyle h_{q}=L_{q}(g^{q-1}{\text{ mod }}q^{2})^{-1}{\text{ mod }}q}$

ואז תהליך הפענוח הוא כדלהלן:

${\displaystyle m_{p}=L_{p}(c^{p-1}{\text{ mod }}p^{2})h_{p}{\text{ mod }}p}$

${\displaystyle m_{q}=L_{q}(c^{q-1}{\text{ mod }}q^{2})h_{q}{\text{ mod }}q}$

${\displaystyle m=CRT(m_{p},m_{q}){\text{ mod }}n}$

כאשר CRT היא מימוש של פתרון מערכת הקונגרואנציות לפי משפט השאריות הסיני. ובגרסה המהירה יש להחליף את ${\displaystyle p-1}$ ו-${\displaystyle q-1}$ ב-${\displaystyle \alpha }$.

מאפיינים והרחבות

הצפנת פליאיי הורחבה למספר כיוונים^[2]. איוון דמגרד הציע^[3] גרסה שבה המודולוס הוא מהצורה ${\displaystyle n^{s}}$ במקום בחזקת 2. וכן הוצעה גרסה מבוזרת (סכמת סף - threshold cryptography) וכן הוצע מימוש ב-ECC^[4].

הומומורפיזם

סכימות ההצפנת פליאיי ${\displaystyle m\mapsto g^{m}r^{n}}$ וכן ${\displaystyle m\mapsto g^{m+nr}}$, מודולו ${\displaystyle n^{2}}$ הן הומומורפיות מהחבורה הכפלית ${\displaystyle (\mathbb {Z} _{n^{2}}^{*},\times )}$ לחבורה החיבורית ${\displaystyle (\mathbb {Z} _{n},+)}$. בניסוח פורמלי עבור כל ${\displaystyle m_{1},m_{2}\in \mathbb {Z} _{n}}$ ו-${\displaystyle k\in \mathbb {N} }$, פונקציית הצפנה ${\displaystyle E}$ ופונקציית פענוח ${\displaystyle D}$ בהתאמה, מתקיים

${\displaystyle D(E(m_{1})E(m_{2}){\text{ mod }}n^{2})=m_{1}+m_{2}{\text{ mod }}n}$

${\displaystyle D(E(m)^{k}{\text{ mod }}n^{2})=km{\text{ mod }}n}$

${\displaystyle D(E(m_{1})g^{m_{2}}{\text{ mod }}n^{2})=m_{1}+m_{2}{\text{ mod }}n}$

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

הסתרה עצמית

הסתרה עצמית (self blinding) היא התכונה שכל טקסט מוצפן ניתן לשינוי לטקסט מוצפן אחר מבלי שהשינוי ישפיע על הטקסט המקורי, בניסוח פורמלי עבור כל ${\displaystyle m\in \mathbb {Z} _{n}}$ ו-${\displaystyle r\in \mathbb {N} }$ מתקיים

${\displaystyle D(E(m)r^{n}{\text{ mod }}n^{2})=m}$

או

${\displaystyle D(E(m)g^{nr}{\text{ mod }}n^{2})=m}$ במקרה של ההצפנה המהירה.

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

הערות שוליים

1. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes
2. Catalano, Dario, Rosario Gennaro, Nick Howgrave-Graham, and Phong Q. Nguyen (2001). “Paillier’s cryptosystem revisited.” Proceedings of the 8th ACM conference on Computer and Communications Security ACM Press, New York, 206–214
3. Damgard, Ivan and Mads Jurik (2001). “A generalization, a simplification and some applications of paillier’s probabilistic public-key system.” Public Key Cryptography—PKC 2001, Lecture Notes in Computer Science, vol. 1992, ed. K. Kim. Springer-Verlag, Berlin, 119–136.
4. Galbraith, Steven D. (2002). “Elliptic curve paillier schemes.” Journal of Cryptology, 15 (2), 129–138.