אלגוריתם Luhn הוא הסיבה שמספר כרטיס מסתיים בספרה שנראית שרירותית. זהו סכום ביקורת—תמצית חשבונית קטנה של כל ספרה שלפניו—והוא הבדיקה האוטומטית הנפוצה ביותר שמספר כרטיס חייב לעבור לפני כל דבר אחר. הוא פותח ב-IBM בשנות החמישים על ידי הנס פטר לון, ולימים הפך למוסכמה בכרטיסי תשלום דרך התקן הבינלאומי שמסדיר את מספור הכרטיסים.
המאמר הזה מסביר למה משמשת ספרת הביקורת, איך מחשבים אותה על נייר, למה היא תופסת את רוב שגיאות ההקלדה, ולמה מעבר שלה אומר הרבה פחות ממה שמקובל להניח.
מה עושה אלגוריתם Luhn
לוקחים מספר כרטיס, מניחים בצד את הספרה האחרונה, ומעבירים את הספרות שנותרו דרך הליך קבוע. התוצאה קובעת מה הספרה הסוגרת חייבת להיות. מספר מתקבל כשהספרה הסוגרת עקבית עם כל מה שלפניה.
שום דבר בהליך הזה אינו מערב בנק, רשימת חשבונות או סוד. זו אריתמטיקה שמפורסמת בספרי לימוד, מיושמת כמעט בכל שפת תכנות, ומחושבת בשבריר מילישנייה. היא עונה בדיוק על שאלה צרה אחת: האם המחרוזת הזו מכילה שגיאת תעתיק ברורה?
קל לשכוח עד כמה הבדיקה הזו צרה. מכיוון שסכום הביקורת הוא הבדיקה האוטומטית הבולטת בטופס תשלום, מתחילים להאמין שהוא אומר יותר ממה שהוא באמת אומר.
איך מחשבים ספרת ביקורת ביד?
ההליך רץ מימין לשמאל על הספרות שנותרו לאחר הסרת הספרה הסוגרת.
- רושמים את הספרות וממספרים את מיקומן מימין, החל מאחת.
- מכפילים כל ספרה שנמצאת במיקום זוגי.
- אם ערך מוכפל עולה על תשע, מחסירים ממנו תשע—כמו לחבר את שתי הספרות של התוצאה.
- מחברים את כל הערכים.
- מחשבים כמה צריך להוסיף כדי להגיע לכפולה הבאה של עשר. הסכום הזה הוא ספרת הביקורת.
דוגמה קצרה ממחישה זאת. ניקח את חמש הספרות 1, 2, 3, 4 ו-5 כגוף של מספר ארוך יותר ונמספר אותן מימין: 5 במיקום ראשון, 4 במיקום שני, 3 במיקום שלישי, 2 במיקום רביעי ו-1 במיקום חמישי. הכפלת המיקומים הזוגיים הופכת את 4 ל-8 ואת 2 ל-4. הערכים הם אפוא 1, 4, 3, 8 ו-5, שסכומם 21. הכפולה הבאה של עשר היא 30, ולכן ספרת הביקורת היא 9 והרצף המוגמר מסתיים ב-9.
ביצוע החישוב ביד עבור מספר כרטיס מלא מייגע אך אינו דו-משמעי. תוכנה עושה זאת בהליכה על המחרוזת מסופה, וזו גם הסיבה שמימוש שמתחיל מהצד הלא נכון ידחה מספרים תקינים לחלוטין.
למה הכפלה תופסת ספרות שהוחלפו?
כלל ההכפלה אינו שרירותי. הוא הופך את המשקל של כל ספרה לתלוי במיקומה, כך שהחלפה בין שתי שכנות משנה בדרך כלל את הסכום.
לכך יש חשיבות מפני ששתי שגיאות האדם הנפוצות ביותר בשדה מספרי הן הקלדה שגויה של ספרה אחת והחלפת מקום של שתי ספרות סמוכות. ספרה אחת שגויה מזיזה את הסכום בשיעור שאינו אפס, ולכן סכום הביקורת נכשל כמעט תמיד. החלפה בין שכנות מזיזה את הסכום גם היא, כי אחת מהשתיים הוכפלה והשנייה לא.
כמעט תמיד, ולא תמיד. כמה החלפות בלתי נראות לבדיקה הזו. הנקודה העיוורת הקלאסית היא הזוג אפס ותשע זה לצד זה: הכפלת תשע והפחתת תשע מהתוצאה מחזירה תשע, ולכן השתיים יכולות להחליף מקום בלי לשנות את הסכום. זוגות אחרים מתנהגים באותו אופן. התיאור המדויק של הבדיקה הוא אפוא שהיא תופסת כל שגיאת ספרה בודדת ואת רוב ההחלפות הסמוכות, אך לא את כולן.
מה ספרת הביקורת אינה מוכיחה
היא אינה יכולה לומר אם מספר הוא אמיתי. שום דבר באריתמטיקה אינו מתייחס למנפיק, ולכן כל קידומת יכולה להצטרף לכל ספרות אמצעיות ולספרת ביקורת סוגרת תקינה שמחושבת בהתאם.
היא אינה יכולה לומר שחשבון פעיל, שהכרטיס לא בוטל, או שמי שמקליד את המספר מחזיק בכרטיס. כל אחת מהשאלות האלה דורשת בקשת אישור למנפיק, וזו בדיוק הפעולה שסביבת בדיקה חייבת להימנע ממנה.
היא גם אינה יכולה לערוב לתאריך התוקף, לשם בעל הכרטיס או לקוד האבטחה. השדות האלה יושבים לצד ספרת הביקורת עם כללים משלהם, ומספר שעומד בסכום הביקורת יכול להיות משודך לתאריך שכבר עבר ולקוד שאינו מתאים לדבר.
זה התיאור הישר של מה שהמחולל באתר הזה מחזיר: כל ערך תקף מבנית ועקבי עם סכום הביקורת הזה, וכל אחד מהם הוא מספר שלא הונפק לאיש מעולם. השימוש בהם הוא לבדיקות תוכנה בלבד.
איפה עוד מופיע אותו סכום ביקורת
כרטיסי תשלום הם המשתמש המוכר ביותר של השיטה הזו, אך לא היחיד. תכניות מספור שזקוקות לשמירה זולה מפני שגיאות הקלדה נוטות להשתמש באותה אריתמטיקה ציבורית, ובכללן כמה מספרי זהות לאומיים, מערכות נקודות ומתנות שונות, ומזהים פנימיים שונים.
לשימוש החוזר הזה יש השלכה מעשית. פונקציית עזר משותפת שמתייחסת לסכום ביקורת שעבר כהוכחה לכרטיס אשראי תסווג שגוי כל דבר אחר שבמקרה עומד בו. כדאי לקרוא לשגרה לפי מה שהיא עושה—סכום ביקורת מודולו עשר—ולא לפי התחום שבו פגשנו אותה לראשונה.
למפתחים: סדר הבדיקות ומלכודות נפוצות
סדר האימות חשוב יותר ממה שמצפים, וסכום הביקורת אינו המקום הנכון להתחיל בו.
בודקים קודם אורך, כי להליך אין דעה על כמה ספרות הועברו לו; קטע בן חמש ספרות יכול להיות עקבי עם סכום הביקורת ובכל זאת חסר תועלת. בודקים אחר כך את מערך התווים, כך שאותיות, רווחים תועים ומפרידים נדחים לפני שרצה אריתמטיקה. מחשבים את סכום הביקורת לאחר מכן, ורק אז מנסים לזהות רשת לפי הקידומת.
שלוש מלכודות חוזרות שוב ושוב:
- התייחסות לאפס מוביל כלא משמעותי. מספרי כרטיס הם מחרוזות, לא מספרים שלמים, ופענוח מספרי יכול להפיל ספרה בשקט ולהפיק כשל בסכום ביקורת שאין לו דבר עם הקלדת המשתמש.
- הרצת מעבר ההכפלה מהשמאל. המיקום מוגדר מימין, ולכן הכיוון הוא חלק מהמפרט ולא פרט מימוש.
- דיווח על סכום ביקורת שנכשל ככרטיס שנדחה. המשמעות היא קלט פגום, וההודעה שמוצגת למשתמש צריכה לומר זאת.
לנתוני בדיקה, התבנית השימושית היא לשמור זוגות: מספר שעובר ואותו מספר עם ספרה אחת ששונתה כך שייכשל. זה נותן למערך מקרה חיובי ומקרה שלילי שנבדלים בתו אחד בדיוק, וכך רגרסיה בולטת במבט אחד. מדריך התבנית מכסה את כללי האורך והקידומת שצריכים לרוץ לפני סכום הביקורת, ומסלול האימות מרכיב את כל הרצף בסדר הנכון.
בדיקת סכום ביקורת מול מחרוזת אמיתית
הדרך המהירה ביותר לבנות אינטואיציה היא להעביר כמה מחרוזות דרך מחולל מספרי הכרטיס. יש להפיק אצווה, לשנות ספרה אחת ביד ולראות את הבדיקה נכשלת; להפיק שוב ולהבחין שרק הספרה הסוגרת זזה בעוד כל מה שלפניה נותר קבוע. השוואת הרשתות היא ההמשך הראוי, כי אותה אריתמטיקה מתנהגת אחרת בתכניות בנות חמש עשרה ספרות ובנות שש עשרה, וההבדל מכשיל פונקציות עזר שנכתבו ביד. כל המספרים שמפיק הכלי באתר הזה נועדו לבדיקות תוכנה בלבד.
צעדים הבאים
יש לרשום את סדר האימות לפני כתיבת הקוד, כשסכום הביקורת שני מהסוף, ולשמור מתקן מקולקל בכוונה לכל מספר תקין במערך. כשרוצים לראות כיצד אורכים וקידומות משתלבים עם הספרה הסוגרת, ממשיכים לתבנית מספר כרטיס.