home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / rec / puzzles / 8174 < prev    next >
Encoding:
Text File  |  1992-12-31  |  3.4 KB  |  100 lines
  1. Xref: sparky rec.puzzles:8174 can.general:6196
  2. Newsgroups: rec.puzzles,can.general
  3. Path: sparky!uunet!cis.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!princeton!csservices!volkl!egs
  4. From: egs@cs.Princeton.EDU (Emin Gun Sirer)
  5. Subject: Re: GST registration number check digit: puzzle and prize
  6. Message-ID: <1992Dec31.232852.2665@csservices.Princeton.EDU>
  7. Originator: egs@volkl
  8. Sender: news@csservices.Princeton.EDU (USENET News System)
  9. Reply-To: egs@cs.Princeton.EDU (Emin Gun Sirer)
  10. Organization: Department of Computer Science, Princeton University
  11. References: <1992Dec31.044137.22920@sq.sq.com>
  12. Date: Thu, 31 Dec 1992 23:28:52 GMT
  13. Lines: 85
  14.  
  15. dave@lsuc.on.ca (David Sherman) writes:
  16. >Virtually all businesses in Canada are registered for the Goods and
  17. >Services Tax (GST) and receive a registration number, which is "R"
  18. >followed by nine digits.
  19. >
  20. >Included in the 9 digits is a check digit.  Revenue Canada Excise,
  21. >which administers the GST, refuses to release the formula for the
  22. >check digit, stating that it "relates to an internal procedure for
  23. >verifying registration numbers".
  24.  
  25. >R123965659    R130134310    R111046959
  26.  [other examples elided to please inews]
  27.  
  28.  
  29.     I believe the last digit is the checksum and and is calculated
  30. according to Luhn's formula. This is the exact same technique used in
  31. computing the last digit of credit card numbers.
  32.  
  33.     The last digit is equal to the ten's complement of the sum of twice
  34. each digit modulo ten. Last time this came up in sci.crypt, someone posted
  35. the following piece of code to calculate them [code appended at the very end].
  36.  
  37.     Here's a check:
  38. ;a.out 12396565 12142551 12159807 11019143 13013431 11104695
  39. 12396565 - 9
  40. 12142551 - 6
  41. 12159807 - 2
  42. 11019143 - 4
  43. 13013431 - 5
  44. 11104695 - 9
  45. ;a.out 10097678 12156037 11104695 10635306
  46. 10097678 - 6
  47. 12156037 - 9
  48. 11104695 - 9
  49. 10635306 - 3
  50.  
  51.     I'll go one step forward and contend that the 130134310 is a typo
  52. (or perhaps a typo on the part of the receipt publisher or perhaps is not
  53. very readable). 
  54.  
  55.     There really is nothing magical about this formula, but knowing
  56. it, one could construct credit card numbers (and perhaps GTEs) that seem
  57. valid.
  58.  
  59. Gun.
  60. #include <stdio.h>
  61. /*
  62.  * >     I am looking for any pointers to information on the algorithms used
  63.  * >to verify credit cards (and similar authentication schemes).  For example,
  64.  * >I know that the last digit on most credit cards is typically a checksum.
  65.  * >What is this method actually called?  Is is a commercial standard?
  66.  * 
  67.  * It is called Luhn's formula.  The last digit is the ten's complement of
  68.  * the modulo sum of the other digits where each other digit is doubled.
  69.  * There is an international standard specifying the number codes, and
  70.  * their allocation.  The following routine will calculate the checksum 
  71.  * number:
  72.  */
  73. /*
  74.  * Return last digit of a bank card (e.g. credit card)
  75.  * Receives all the digits, but the last one as input
  76.  * By Diomidis Spinellis <dds@doc.ic.ac.uk>
  77.  */
  78. int bank(char *u) {
  79.         register i, s = 0;
  80.         int l, t;
  81.  
  82.         l = strlen(u);
  83.         for(i = 0; i < l ; i++) {
  84.                 t = (u[l - i - 1] - '0') * (1 + ((i + 1) % 2));
  85.                 s += t < 10 ? t : t - 9;
  86.         }
  87.         return 10 - s % 10;
  88. }
  89.  
  90. void main(int argc, char *argv[]) {
  91.     int i;
  92.     if(argc <= 1) {
  93.     fprintf(stderr,"Usage: %s bankcardno\n", argv[0]);
  94.     exit(1);
  95.     }
  96.     for(i = 1; i < argc; ++i)
  97.     printf("%s - %d\n", argv[i], bank(argv[i]));
  98.     exit(0);
  99. }
  100.