Credit Cards and Luhn Algorithm | CS50 Week 1

cs50 강의를 한글로 번역한것입니다.

Credit Cards

크레딧카드는 플라스틱으로 된 카드이다 (물론 요즘에는 모바일로도 가능하다). 사고싶은 물건이나 서비스를 현급 없이도 사용할 수 있다. 크레딧카드(또는 체크카드)를 보면 숫자들이 써져있는데, 그 숫자들은 세계 어디엔가 있는 데이터베이스에 저장되어있다. 그래서 내가 무언가를 구매하면, creditor는 어디에 청구를 해야할지 아는것이다.

세상엔 수많은 사람들이 Credit Cards를 사용하고있기 때문에, 이 카드번호들은 상당히 길다. 대표적으로 글로벌하게 쓰이는 American Express는 15 digits을 쓰고, MasterCards는 16-digits, 그리고 VISA는 13 또는 16-digits를 사용한다. 그리고 이 숫자들은 binary가 아닌 decimal numbers, 즉 0-9까지 숫자들을 사용한다. 그러니까 아맥스(Amex, 또는 American Express)는 아래와 같이 다른 카드를 발급할 수 있다. 1000조!!!

10^15 = 1,000,000,000,000,000

사실, 이것은 조금 과장된것인데, 크레딧카드마다 숫자에 어떤 규칙이 존재한다. 모든 American Express 카드 숫자들은 34 또는 37로 시작한다. MasterCards는 51, 52, 53, 54 또는 55로 시작한다. 모든 VISA카드는 4번으로 시작한다. 이뿐만이 아니다. 크레딧 카드에는 checksum이라는것도 존재하는데, 두 숫자에 대한 수학적 관계를 뜻한다. checksum은 오타나 가짜 숫자들을 방지하는데, 데이터베이스에서 쿼리해서 검색하지 않아도 가능하다. DB에서 검색을 해오는것은 꽤 시간이 걸리는 일이기 때문에 이러한 방식을 사용한다. 물론, 똑똑한 수학천재라면 이러한점도 파악해서 가짜 카드번호를 생성할 수 있겠지만, 데이터베이스에서도 다시한번 엄격하게 체크를 한다.

 

 

Luhn's Algorithm

그래서, 카드번호를 만들어내는 비밀의 공식은 무엇일까? 대부분의 카드는 IBM사의 Hans Peter Luhn이라는 사람이 개발한 알고리즘을 사용한다. 이것을 룬의 알고리즘이라고 부르는데, 어떠한 번호들이 유효한 값인지 간단하게 검사하는 알고리즘이다. 공식은 다음과 같다. 다음과 같은 예시 번호를 사용해보자. 이 번호는 가상의 David이라는 사람의 VISA 카드이다.

4003600000000014

1. 첫번째 digit부터 하나씩 걸러서 그 숫자에 2씩 곱해서 결과물에 나온 digits를 더해준다.

4003600000000014 -> 밑줄친 숫자를 각각 2씩 곱해서 더해주는 계산을 해주면 된다: 1•2 + 0•2 + 0•2 + 0•2 + 0•2 + 6•2 + 0•2 + 4•2 곱셈을 먼저 해주면: 2 + 0 + 0 + 0 + 0 + 12 + 0 + 8 그리고 이 결과물의 digits를 더해주면: 2 + 0 + 0 + 0 + 0 + 1 + 2 + 0 + 8 = 13

 

2. 숫자를 더한것에 (1)단계에서 사용하지 않았던 숫자들을 더해준다.

13 + 4 + 0 + 0 + 0 + 0 + 0 + 3 + 0 = 20

 

3. 이렇게 계산한 숫자의 마지막 digit이 0이면, 이 숫자는 유효한 카드번호이다.

20 % 10 = 0 마지막 자리수가 0이기때문에, David의 카드 번호는 유효하다!

 

credit.c

사실 Luhn's algorithm 말고도 더 많은 것들을 체크하지만, 일단 룬 알고리즘이 작동하는지 확인하고, 어떤 카드인지 (Visa, MasterCard, JCB, Discover) 몇가지 종류만 검사하는 프로그램을 만들어보자. 모든 코드를 복붙하기는 내용이 복잡해서, 로직만 설명하자면, luhn 알고리즘에서 처음 1번 스텝은 아래와 같이 해결했다.

 

int luhnFirstStep(long number, int len){
    // Incase that card number digit length is even, divide by 10, so we will get every oddth place number from the left.
    if(len % 2 == 0){
        number /= 10;
    }

    int sum = 0;
    while(number > 0){
        // Divide by 10 and get the remainder, then multiply by 2
        int temp = (number % 10) * 2;

        // To add 2 digits (or 1), divide by 10 to get the first digit then modulus by 10 to get the remainder, and then add to sum
        sum += (temp / 10) + (temp % 10);

        // Divide by 100, to get the next digit to work
        number /= 100;
    }
    return sum;
}

long의 길이를 알기 위해 미리 길이를 세두었고, 숫자 계산이 뒤쪽부터 이루어져야하기 때문에 뒤에서부터, 홀수번째 자리를 찾아서 2로 곱한 후 그 digits 들을 sum에 더하는 방식이었다. 

 

두번째도 유사하다.

int luhnSecondStep(long number, int sum, int len){
    if(len % 2 == 1){
        number /= 10;
    }
    while(number > 0){
        sum += number % 10;
        number /= 100;
    }
    return sum;
}

이번엔 짝수번째인 맨 뒷자리를 찾아서 그 digits을 sum에 더해주고, 그다음 짝수번째 자리로 가는식으로 계산했다.

 

bool isValidCardNumber(long number, int len){
    return luhnSecondStep(number, luhnFirstStep(number, len), len) % 10 == 0;
}

이후, 이 두 functions를 사용해서, 맨 끝자리가 0인지 검사하는 방식이었다. 그리고 getCardType이라는 함수를 만들어서 첫 두자리 (비자의 경우에는 첫번째자리만) 검사해서, 조건에 맞는지 출력했고, 만약 정보에 없으면 Unknown으로 찍었다. 실제라면 이 정보들이 DB에 저장되어있어서 가져오는것이 맞을것이다. 컴파일 후 Paypal에서 제공하는 카드정보들로 테스트를 해보면,

> make credit
clang     credit.c  -lcs50 -o credit
> ./credit
Number: 4111111111111111
VISA
> ./credit
Number: 3566002020360505
JCB
> ./credit
Number: 6011000990139424
Discover
> ./credit
Number: 6176292929
INVALID
> ./credit
Number: 4003-6000-0000-0014
Number: visa
Number: VISA
Number: 4003600000000014
VISA
> ./credit
Number: 2223000048400011
Mastercard
> ./credit
Number: 5105105105105100
Mastercard
> ./credit
Number: 30569309025904
Unknown

잘 작동하는것을 보여준다. 아직 등록되어있지 않은 카드사 정보는 Unlown으로 나온다.

 

 

Reference

Test Payflow Transactions

 

Test Transactions

 

Credit - CS50