מחשבון אלגוריתם לון - אימות כרטיסי אשראי ו-IMEI

מהו אלגוריתם לון?

אלגוריתם לון, המכונה גם אלגוריתם מודולו 10, הוא נוסחה שבודקת אם מחרוזת ספרות יכולה להיות מספר זיהוי תקף. משתמשים בו כדי לזהות שגיאות הקלדה במספרי כרטיסי אשראי, במספרי IMEI בטלפונים ובקודי זיהוי אחרים, לפני שהן גורמות לשגיאה. מהנדס IBM הנס פטר לון תיאר את השיטה בפטנט שהוגש בשנת 1954.

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

כיצד מחשבים סכום ביקורת לפי לון

הבדיקה פועלת על ספרות המספר, בקריאה מימין לשמאל.

1. מתחילים בספרה השנייה מימין ומכפילים כל ספרה שנייה ב־2.
2. אם הכפלת ספרה נותנת מספר גדול מ־9, מחסרים ממנו 9. (זו אותה תוצאה כמו חיבור שתי הספרות של התוצאה, ולכן 16 הופך ל־1 + 6 = 7, או לחלופין 16 − 9 = 7.)
3. מחברים את כל הספרות: את הספרות שהוכפלו, לאחר ההתאמה, ואת הספרות שלא שונו.
4. אם הסכום הכולל מתחלק ללא שארית ב־10, המספר תקף. אחרת, הוא אינו תקף.

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

דוגמה פתורה: אימות מספר כרטיס

ניקח את מספר הבדיקה 4532015112830366.

1. ספרות מימין לשמאל: 6, 6, 3, 0, 3, 8, 2, 1, 1, 5, 1, 0, 2, 3, 5, 4
2. הכפלת כל ספרה שנייה: 6, 12, 3, 0, 3, 16, 2, 2, 1, 10, 1, 0, 2, 6, 5, 8
3. מחסרים 9 מכל תוצאה הגדולה מ־9: 6, 3, 3, 0, 3, 7, 2, 2, 1, 1, 1, 0, 2, 6, 5, 8
4. מחברים: 6+3+3+0+3+7+2+2+1+1+1+0+2+6+5+8 = 50
5. 50 מתחלק ב־10, ולכן המספר תקף.

דוגמה פתורה: מספר שאינו תקף

ניקח את 490154203237517, מספר בן 15 ספרות בפורמט המשמש מספרי IMEI.

ביצוע אותם שלבים נותן סכום של 59. מכיוון ש־59 אינו מתחלק ב־10, המספר הזה אינו תקף.

כדי להפוך אותו למספר תקף, צריך לשנות רק את הספרה האחרונה. בדיקת כל ספרה אפשרית בסוף מראה שספרה אחרונה 8 מעלה את הסכום ל־60, שמתחלק ב־10. לכן 490154203237518 הוא מספר לון תקף, בעוד שכל ספרה אחרונה אחרת מ־0 עד 9 (מלבד 8) יוצרת מספר שאינו תקף.

כיצד להשתמש במחשבון זה

למחשבון יש שני מצבים, שנבחרים באמצעות לחצני הפעולה.

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

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

מתעלמים מרווחים, מקפים ונקודות בקלט, ולכן "4532 0151 1283 0366" ו־ "4532-0151-1283-0366" נקראים באותה דרך כמו הספרות ללא מפרידים. כל תו אחר, כגון אות, נדחה ומוצגת הודעת שגיאה.

היכן משתמשים באלגוריתם לון

• כרטיסי תשלום. Visa, Mastercard, American Express ורשתות אחרות בונות את מספרי הכרטיסים שלהן כך שהמספר המלא יעבור את בדיקת לון. טפסי תשלום יכולים להשתמש בכך כדי לזהות ספרה שהוקלדה שגוי לפני הפנייה למעבד תשלומים.
• מספרי IMEI. המזהה בן 15 הספרות, המוקצה לטלפונים ולמכשירים סלולריים אחרים, כולל ספרת ביקורת של לון.
• מספרי ביטוח לאומי קנדיים. מספר ה־SIN בן 9 הספרות משתמש באותה בדיקה.
• מזהה ספק שירותי הבריאות הלאומי בארצות הברית (NPI). ספקי שירותי בריאות בארצות הברית מקבלים NPI בן 10 ספרות, המאומת באמצעות בדיקה המבוססת על לון.

מה אלגוריתם לון אינו מזהה

האלגוריתם תמיד מזהה ספרה יחידה שהוקלדה שגוי, בלי קשר לספרה או למיקומה. הוא גם מזהה כל החלפה של ספרות סמוכות (כמו הקלדת "39" במקום "93"), למעט מקרה מסוים אחד: החלפת 0 ו־9 הסמוכות זו לזו, כגון הפיכת "09" ל־"90".

הוא גם אינו מזהה שלוש שגיאות "תאומות", שבהן זוג ספרות זהות מוחלף בזוג זהה אחר: 22 שנקרא כ־55, 33 שנקרא כ־66, ו־44 שנקרא כ־77. מכיוון שהפערים האלה ידועים ומוגבלים, בדיקת לון אמינה לזיהוי שגיאות הקלדה רגילות, אך אינה נחשבת כשלעצמה למערכת מלאה לזיהוי שגיאות.

לון אינו בדיקת אבטחה

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

אימות מספר ב־JavaScript

1function isValidLuhn(number) {
2  const digits = number.replace(/\D/g, '').split('').map(Number);
3  if (digits.length === 0) return false;
4
5  let sum = 0;
6  let doubleDigit = false;
7  for (let i = digits.length - 1; i >= 0; i--) {
8    let d = digits[i];
9    if (doubleDigit) {
10      d *= 2;
11      if (d > 9) d -= 9;
12    }
13    sum += d;
14    doubleDigit = !doubleDigit;
15  }
16  return sum % 10 === 0;
17}
18

הבדיקה שמונעת קלט ריק חשובה: למחרוזת ריקה יש סכום ספרות של 0, ו־0 מתחלק ב־10, ולכן בלי הבדיקה הפונקציה הייתה מחשיבה בטעות כלום כ־ מספר תקף. כדי למצוא ספרת ביקורת במקום לבדוק אחת, מריצים את אותה לולאה על הספרות שלפני ספרת הביקורת, אך מתחילים להכפיל מהאחרונה שבהן, ולאחר מכן מחשבים את (10 - sum % 10) % 10.

שאלות נפוצות

למה משמש אלגוריתם לון?

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

עד כמה אלגוריתם לון מדויק בזיהוי שגיאות?

הוא מזהה כל ספרה יחידה שהוקלדה בשגוי וכמעט כל מקרה של החלפת שתי ספרות סמוכות. ההחלפה היחידה שהוא אינו מזהה היא של 0 ו־9 הסמוכות זו לזו. הוא גם אינו מזהה שלוש החלפות "תאומות" מסוימות: 22 במקום 55, 33 במקום 66, ו־44 במקום 77.

האם מספר לון תקף פירושו שהכרטיס אמיתי?

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

האם אפשר לבצע את בדיקת לון ללא מחשב?

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

האם המספרים שנוצרו הם מספרי כרטיס אמיתיים?

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

מדוע הוא נקרא אלגוריתם מודולו 10?

מכיוון שהשלב האחרון בודק אם הסכום מתחלק ללא שארית ב־10, דבר שנכתב במתמטיקה כך: "sum mod 10 = 0". "Mod" הוא קיצור של modulo, השארית שנותרת לאחר חילוק.

מי המציא את אלגוריתם לון?

הנס פטר לון, מהנדס ב־IBM, תיאר אותו בבקשת פטנט שהוגשה בשנת 1954 (והוענקה בשנת 1960 כפטנט אמריקאי 2,950,048). הוא ידוע גם בעבודתו המוקדמת על יצירת אינדקסים ממוחשבים לטקסט.