באוגוסט 1941 הגיעה להורוכוב יחידת איינזצגרופן, ובסיוע אוקראינים מקומיים, רצחה כ-300 יהודים בגן העירוני. בראשית אוקטובר 1941 רוכזו יהודי העיירה בגטו, אליו הובאו בהמשך גם כ-2,000 יהודים מיישובי הסביבה. גטו זה חולק לגטו ל"יעילים" ולגטו ל"בלתי יעילים", והקצאת המזון בו הייתה מזערית. באוקטובר 1941 הובאו לגטו יהודי סנקביצ'ובקה. מעת לעת רצחו הגרמנים יהודים יחידים בגטו.
ב-8 בספטמבר 1942 הובלו כ-5,000 יהודי הגטו לבורות ירי ליד הכפר צ'וייב (Chuyev), ונרצחו שם. ב-3 באפריל 1944 שוחררה הורוכוב בידי הצבא האדום. רק בודדים מיהודיה נותרו בחיים.
לוציפר (צופן)
בקריפטוגרפיה, לוציפר (Lucifer) הוא שם כולל שניתן למשפחה של צפני בלוקים שפיתוחם החל בראשית 1966 במעבדות IBM "תומאס ג'י ווטסון" ביורקטאון ניו-יורק. לוציפר ידוע כצופן הבלוקים הראשון שפותח למטרות אזרחיות ואף נעשה ב-1970 שימוש מסחרי בגרסה אחת שלו במערכת בנקאות אלקטרונית בבריטניה. הצופן הוא אב קדמון של DES ולמעשה כמעט כל הרעיונות נשאבו ממנו לטובת תקן ההצפנה הפדרלי הישן שהוצע לממשלת ארצות הברית ב-1976. כיום הצופן אינו בטוח לשימוש, הוא פגיע להתקפה דיפרנציאלית ועיקר העניין בו הוא לצורך אקדמי. ידוע שה-NSA התערב במהלך פיתוח DES שהיה מבוסס על לוציפר ושינה אחדים מערכי תיבות ההחלפה כדי לחזקו כנגד התקפה דיפרנציאלית.
היסטוריה.
ב-1966 הוחלט ב-IBM לספק ללקוחות החברה שירותי אבטחת מידע תוך שימוש בקריפטוגרפיה וחוזה נחתם עם בנק לוידס לפיתוח מכונת קופאי אוטומטית (ATM) תוך שימוש בקריפטוגרפיה כדי להגן על פעולת המשיכה. בתחילה הוצע לצורך כך צופן היל אך נפסל כי לא היה חזק מספיק. בסופו של דבר התקבל לוציפר שהוצע על ידי הורסט פייסטל, דון קופרשמידט, אלן קונהיים ומדענים נוספים. פייסטל, מהגר ממוצא גרמני שלו רקע צבאי בפיתוח צפנים, היה במקום הנכון בזמן הנכון והסתבר שלפיתוח זה הייתה השפעה עצומה על ההצפנה המודרנית בכלל.
צופן לוציפר יועד בעיקר לחומרה והתבנית הבסיסית שלו הייתה, בהשראת קלוד שאנון אבי תורת האינפורמציה, "צופן מרוכב" המשלב כמה פונקציות חלשות כשלעצמן במבנה פייסטל. הרעיון היה בשעתו חידוש בפני עצמו ואבן דרך בתולדות ההצפנה המודרנית. ההבדלים העיקריים בין הגרסאות השונות שהוצעו על ידי פייסטל נבע בעיקר מגודל הבלוק בסיביות, גודל המפתח בסיביות, מספר התאמות בערכי תיבות ההחלפה וכיוצא בזה. ב-1971 רשם פייסטל פטנט על גרסה אחת שבה אורך הבלוק והמפתח היה 48 סיביות. John L. Smith פרסם גרסה אחרת המשתמשת בבלוק באורך 32 סיביות ומפתח 64 סיביות. ב-1973 פרסם פייסטל בסיינטיפיק אמריקן את הגרסה החזקה ביותר של הצופן הפועלת על בלוקים באורך 128 סיביות ועם מפתח באורך 128 סיביות. גרסה דומה תוארה על ידי ארתור סורקין (להלן) הפועלת עם 16 סבבים. כמו כן פורסם מימוש שלו לתוכנה בשפת APL. כאמור הצופן אינו בטוח לשימוש בסטנדרטים של ימינו והעניין בו אקדמי בלבד.
השם "לוציפר" נובע ממשחק מילים של כינוי הפרויקט של פייסטל שנקרא הדגמה של מערכת פרטיות שמתחיל במילה "Demonstration" השם קוצר ל-"Demon" כיוון שהמחשב שעליו עבד לא תמך בשמות ארוכים. ואז הוצע להחליף את Demon (בעל צליל דומה לשד או שטן באנגלית) ללוציפר.
מבנה כללי.
לוציפר הוא "צופן מרוכב" הכולל הרכבה של מספר טרנספורמציות חלשות, באופן כזה ששילובן יחד במספר חזרות מתאים יוצר פונקציית הצפנה חזקה. הפונקציות הן:
חוזרים על הפעולות הללו לפי סדר זה מספר פעמים, כאשר הפלט מסבב אחד הופך קלט לסבב הבא וכן הלאה והתוצאה האחרונה היא פלט הצופן הסופי.
המפתח מספק "סודיות", ההחלפה מספקת "ערבוב" ואילו התמורה מספקת "פיזור", שלוש התכונות הללו כשהן משולבות יחד יוצרות אפקט כדור שלג, כל שינוי בסיבית אחת בבלוק הקלט גורר אחריו תוך מספר מועט של סבבים לשינוי של לפחות מחצית מסיביות בלוק הפלט. היות שכל הפעולות תלויות במפתח הסודי קשה מאוד להתחקות אחר השינויים שעברו סיביות המסר ללא ידיעת המפתח.
היות שהצופן תוכנן לחומרה הייתה חשיבות רבה לשטח שהוא מאכלס, המתבטא במספר השערים במעגל המשולב. כדי לחסוך במקום העלה פייסטל רעיון שהיה חידוש בשעתו, לתכנן את ההצפנה באופן כזה שאותם מעגלים המשמשים להצפנה ישמשו לפענוח בשינוי קל ומבלי צורך להקצות חומרה נפרדת לפענוח. הרעיון הוא לחלק את המידע לשני חצאים, מחצית אחת משמשת קלט לפונקציה כלשהי שהפלט שלה משמש כמפתח הצפנה להצפנת המחצית השנייה באמצעות XOR ולאחר מכן הם מחליפים מקומות וחוזרים שוב, כמו טווייה. בסבב אחד רק מחצית אחת משתנה ואילו השנייה נותרת ללא שינוי. בפענוח "פורמים" את ההצפנה בתהליך זהה אך בסדר הפוך מההצפנה, מהסוף להתחלה.
בסבב אחד קל לראות שהמבנה הוא פרמוטציה הפיכה כי מתקיים:
הסימן formula_2 הוא XOR. כלומר כיוון ש-XOR הופכי של עצמו לכן formula_3 היא אינוולוציה. מזה נובע שאפשר להפוך את ההצפנה פשוט על ידי חזרה על אותה פעולה.
לוציפר 2984.
תיאור הצופן בגרסה של אלן קונהיים שהיה בצוות הפיתוח, שתוארה בספרו Computer Security and Cryptography. לטענתו זוהי הגרסה המסחרית היחידה של הצופן שהוטמעה במכונה IBM 2984 Cash Issuing Terminal שהייתה מהכספומטים הראשונים שיוצרו עבור בנקים באנגליה. לפי גרסה זו בלוק הקלט בגודל formula_4 סיביות (בסך הכול 8 ספרות הקסדצילמיות), המפתח בגודל formula_5 סיביות, הצופן מבוצע עם 16 סבבים והוא פועל ברמה של "ניבלים" שהם חצאי בתים בגודל 4 סיביות (כל ניבל מיוצג על ידי ספרה הקסדצימלית אחת).
בלוק המסר מחולק תחילה לשני חצאים formula_6 ו-formula_7 כל אחד בגודל 16 סיביות (4 ניבלים) אותם טוענים לתוך אוגרי דטה מתאימים ומבצעים 16 פעמים:
הפונקציה formula_14 מתנהגת כטרנספורמציה אי-ליניארית על קלט של 16 סיביות. ובכל סבב משתמשים בסך הכול ב-36 סיביות מהמפתח. כך שכל סיבית מפתח מנוצלת 9 פעמים. 36 סיביות המפתח משולבות בכל סבב באופן הבא; 16 מהן לצורך פעולה 2.1, 4 מהן לצורך פעולה 2.2 ו-16 האחרונות לצורך פעולה 2.3. לאחר מכן "מסובבים" את המפתח.
הכנת המפתח.
תהליך הכנת המפתח פשוט בתכלית. תחילה טוענים את 64 סיביות המפתח הסודי המסופק על ידי המשתמש לאוגר בזיכרון. בחלוקה לניבלים מתקבלים בסך הכול 16 ניבלים הממוספרים מ-0 עד 15. מבצעים פעולת הזזה מעגלית בסיביות שמאלה 28 פעמים (או 7 ניבלים), בכל פעימה הסיבית הנפלטת מצד שמאל מוחזרת מצד ימין. מתוך 16 הניבלים משתמשים בכל סבב רק בתשעה מהם המסומנים באותיות formula_15 עד formula_16. למשל בסבב 2 משתמשים בניבלים 6,5,4,3,2,1,0,15,14 לפי סדר זה (מסמנים ב-formula_15 את הערך המצוי בניבל מס' 14 וכן הלאה עד formula_16). סיביות המשתנים formula_19 משולבות בפעולה 2.1. סיביות המשתנה formula_15 משמשות לצורך תיבות ההחלפה בפעולה 2.2. סיביות המשתנים formula_21 משולבות בפעולה 2.3. ובכל סבב כל סיביות המפתח מוזזות שוב בהזזה מעגלית לשמאל 28 פוזיציות. כל התהליך מסתכם בטבלה הבאה:
תיבות החלפה S.
תיבות ההחלפה הן שתי פונקציות אי-ליניאריות המסומנות formula_22 בהתאמה. לצורך פונקציות אילו מכינים שתי טבלאות החלפה לכל 16 הניבלים האפשריים, בסך הכול 64 סיביות. סיביות המשתנה formula_15 קובעות האם להשתמש בתיבה 0 (שורה שלישית בטבלה) או בתיבה 1 (שורה רביעית) עבור כל אחד מארבעת הניבלים של הקלט בהתאם. למשל אם הסיבית הראשונה של formula_15 היא אפס וערכו של הניבל הראשון הוא 'C' (בעשרוני 12) אז הפלט הוא formula_25.
עבור קלט formula_26 באורך 4 ניבלים הפלט הוא:
תיבות תמורה P.
תיבות התמורה הן מיפוי תלוי מפתח של 16 סיביות ל-16 סיביות. התיבות P-box מגדירות כיצד הניבלים formula_28 ו-formula_16 קובעים מה תהיה התוצאה בהתאם. אפשר להתייחס לתיבות התמורה כאל מטריצה בגודל 16 על 16 סיביות כאשר רק הפוזיציות המתאימות לסיביות '1' במשתנים הללו דלוקות וכל היתר מאופסות. הקלט הוא ארבעה ניבלים של דטה; formula_30 האינדקס לסיבית אחת הוא formula_31 כלומר הסיבית formula_32 בניבל formula_16 וכן ארבעה ניבלים של מפתח formula_21. הפלט הוא ארבעה ניבלים formula_35 כאשר כל סיבית פלט מושפעת משתי סיביות דטה ושתי סיביות מפתח מתאימות. למשל הביטוי formula_36 פירושו הכפלה (פעולת AND) של הסיבית הראשונה מניבל הדטה הראשון במשלים של סיבית הראשונה מניבל המפתח formula_16 וחיבור (XOR) עם תוצאת הכפל של הסיבית הראשונה מניבל הדטה השני עם הסיבית הראשונה מניבל המפתח formula_38. כל הסיביות מתחלפות לפי הטבלה הבאה, כאשר הסימון formula_39 הוא פעולת השלילה:
למעשה אף על פי שמן, תיבות התמורה של לוציפר הן טרנספורמציה ליניארית לפי מפתח ולא תמורה.
לוציפר 128.
ב-1983 פרסם ארתור סורקין במגזין קריפטולוגיה את הגרסה החזקה ביותר של צופן לוציפר. הבלוק באורך 128 סיביות ומפתח הצופן באורך 128 סיביות. הפונקציה הפנימית בנויה מטנרספורמציה ליניארית וטרנספורמציה אי-ליניארית המבוצעות לסירוגין בשילוב עם מפתח ההצפנה. בעבר היו שסברו שהוא חזק מ-DES כיוון שאינו מכיל את החולשות הידועות שלו שהם; המפתח הקצר (רק 56 סיביות) והעובדה ששיקולי הפיתוח שלו היו סוד לאומי בזמנו מה שהעלה חשד כי היו בו חולשות הידועות רק למפתחיו ול-NSA, מה שאי אפשר לומר לגבי לוציפר. הגרסה המקורית יועדה לחומרה והיא שולבה בכרטיס IBM 2770 כחלק מניסוי. משום שהחומרה הייתה מוגבלת נעשה מאמץ לפשט את הצופן במידת האפשר. גרסת התוכנה שלה שנכתבה בפורטרן במקור מתוארת להלן בפסאודו-קוד.