맨위로가기

룬 알고리즘

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

룬 알고리즘은 체크 디지트를 포함하는 숫자의 유효성을 검증하는 데 사용되는 간단한 체크섬 알고리즘이다. 이 알고리즘은 숫자의 각 자릿수에 특정 규칙을 적용하여 계산된 값을 통해 유효성을 판단하며, 신용 카드 번호, IMEI 번호, 주민등록번호 등 다양한 식별 번호 체계에 활용된다. 룬 알고리즘은 구현이 용이하고 널리 사용되지만, 특정 유형의 오류는 감지하지 못하는 단점이 있다. 대한민국에서는 신용 카드 번호 및 주민등록번호 등의 유효성 검사에 활용되고 있으며, 개인정보 보호를 위한 기술적 조치로도 사용될 수 있다.

더 읽어볼만한 페이지

  • 체크섬 알고리즘 - MD5
    MD5는 로널드 리베스트 교수가 개발한 128비트 해시 값 생성 암호화 해시 함수이나, 보안 취약점으로 인해 현재는 보안이 중요한 분야에서는 사용이 중단되었다.
  • 체크섬 알고리즘 - 범용 상품 부호
    범용 상품 부호(UPC)는 소매점에서 상품을 식별하기 위해 상품 포장에 인쇄되는 널리 사용되는 바코드의 일종으로, 12자리 숫자로 구성된 UPC-A를 포함한 다양한 변형이 존재한다.
  • 오류 검출 정정 - 부호 이론
    부호 이론은 정보를 효율적으로 표현하고 오류를 감지 및 수정하는 기술을 연구하며, 소스 부호화, 채널 부호화, 암호 부호화 등으로 발전하여 CD, 모뎀, 휴대폰 등 다양한 분야에 응용된다.
  • 오류 검출 정정 - 비터비 알고리즘
    비터비 알고리즘은 잡음이 있는 통신 링크 상에서 길쌈 부호 해독에 사용되며, 확률과 관련된 극대화 문제에 동적 계획법을 적용하는 표준 용어로, 상태 기계를 기반으로 은닉 마르코프 모델에서 가장 가능성 높은 상태 시퀀스를 찾는 데 활용되어 통신, 자연어 처리, 생물정보학 등 다양한 분야에 적용되고 개선 방법이 연구되고 있다.
  • 모듈러 산술 - 이산 로그
    이산 로그는 유한군에서 이산 거듭제곱의 지수를 찾는 역함수로, 소수 p를 법으로 하는 정수 모듈러 곱셈 그룹에서 계산적으로 풀기 어려운 문제이며, 현대 암호 시스템의 안전성 기반이지만 양자 알고리즘으로 효율적 해결이 가능하여 양자 내성 암호 연구가 필요하다.
  • 모듈러 산술 - 중국인의 나머지 정리
    중국인의 나머지 정리는 여러 개의 연립 합동식의 해 존재성과 유일성에 대한 정리이며, 정수론, 대수학, 암호학 등 다양한 분야에 응용된다.
룬 알고리즘
개요
종류체크섬 알고리즘
개발일1954년 1월 6일
발표일1960년 8월 23일
발명가한스 페터 루운
상세 정보
목적간단한 체크섬 수식
활용신용 카드 번호, IMEI 번호 등의 유효성 검사

2. 설명

룬 알고리즘은 체크 디지트를 포함하는 숫자가 올바른지 검증하는 데 사용된다. 체크 디지트는 일반적으로 고유 번호에 부여되며, 체크 디지트를 포함한 전체를 인증 번호 등에 사용한다.[1]

룬 알고리즘은 숫자의 각 자릿수를 오른쪽에서 왼쪽으로 처리한다. 짝수 번째 자릿수는 2배로 만든다. 만약 2배로 만든 값이 9보다 크면, 그 값에서 9를 빼거나 각 자릿수를 더한다. 이렇게 처리된 모든 자릿수의 값을 더한 후, 10으로 나눈 나머지가 0이면 해당 번호는 유효한 것으로 판단한다.

예를 들어, 49927398716이라는 번호가 룬 알고리즘에 의해 올바른지 확인하는 방법은 다음과 같다.

1. 오른쪽 끝에서 짝수 번째 자릿수를 각각 2배 한다: (1×2) = 2, (8×2) = 16, (3×2) = 6, (2×2) = 4, (9×2) = 18

2. 각 숫자의 총합을 계산한다(괄호 안의 숫자는 2배로 한 자릿수): 6 + (2) + 7 + (1+6) + 9 + (6) + 7 + (4) + 9 + (1+8) + 4 = 70

3. 10으로 나누어 떨어지는지 확인한다: 70 mod 10 = 0 이므로, 이 번호는 올바르다.

2. 1. 검증 절차

검증 숫자를 포함한 전체 숫자를 검증하는 방법은 다음과 같다.

# 검증할 숫자의 검사 숫자(마지막 숫자)를 제거한다. (예: 17893729974 → 1789372997)[1]

# 검사 숫자를 계산한다(위 참조).[1]

# 결과를 원래의 검사 숫자와 비교한다. 두 숫자가 일치하면 결과는 유효하다. (예: (주어진 검사 숫자 = 계산된 검사 숫자) ⇔ (유효한 검사 숫자)).[1]

룬 알고리즘은 체크 디지트를 포함하는 숫자가 올바른지 검증한다. 체크 디지트는 일반적으로 고유한 번호에 부여되며, 체크 디지트를 포함한 전체를 인증 번호 등에 사용한다. 이 번호는 다음과 같이 검증할 수 있다.[1]

# 오른쪽 끝의 체크 디지트를 1번째로 하여 짝수 번째 자릿수를 2배로 한다.[1]

# 2배로 하지 않은 자릿수도 포함하여 각 숫자의 총합을 구한다(2배로 한 자릿수가 2자리가 된 경우에는 각각을 별개의 숫자로 더한다).[1]

# 이 총합의 일의 자리가 0이면(즉, 10으로 나누어 떨어지는 경우), 이 번호는 룬 알고리즘에서는 올바르고, 그렇지 않은 경우에는 올바르지 않다.[1]

예를 들어, 49927398716 이라는 번호를 검증하는 경우를 생각해 보자.[1]

# 오른쪽 끝에서 짝수 번째 자릿수를 각각 2배 한다: (1×2) = 2, (8×2) = 16, (3×2) = 6, (2×2) = 4, (9×2) = 18[1]

# 각각의 숫자의 총합을 계산한다(괄호로 둘러싸인 숫자는 위의 단계에서 2배로 한 자릿수): 6 + (2) + 7 + (1+6) + 9 + (6) + 7 + (4) + 9 + (1+8) + 4 = 70[1]

# 10으로 나누어 떨어지는지 조사한다: 70 mod 10 = 0 이므로, 이 번호는 올바르다.[1]

2. 2. 검증 숫자 생성 방법

검증 숫자는 다음과 같이 계산된다.

1. 숫자에서 검증 숫자를 제거한다(이미 있는 경우). 이렇게 하면 페이로드가 남는다.

2. 페이로드 숫자부터 시작한다. 오른쪽에서 왼쪽으로 이동하면서 마지막 숫자부터 시작하여 두 번째마다 숫자를 두 배로 만든다. 숫자를 두 배로 늘린 결과가 9보다 크면 9를 뺀다.

3. 결과 숫자를 모두 더한다(두 배로 늘리지 않은 숫자 포함).

4. 검증 숫자는 (10 - (s mod 10)) mod 10으로 계산되며, 여기서 s는 3단계의 합이다. 이는 s에 추가하여 10의 배수로 만들기 위해 필요한 가장 작은 숫자(0일 수도 있음)이다. 동일한 값을 제공하는 다른 유효한 공식은 9 - ((s + 9)mod 10), (10 - s)mod 10 및 10⌈s/10⌉ - s이다. 공식 (10 - s)mod 10은 나머지 연산이 음수를 처리하는 방식의 차이로 인해 모든 환경에서 작동하지 않는다.

계좌 번호 1789372997(단, "페이로드"이며 아직 검증 숫자는 포함되지 않음)의 예를 가정해 보겠다.

원본 숫자7992739871
곱셈2121212121
곱셈 결과149182143188141
자릿수 합계5992539851



결과 자릿수의 합은 56이다.

검증 숫자는 (10 - (56 mod 10)) mod 10 = 4와 같다.

이렇게 하면 전체 계좌 번호는 17893729974가 된다.

3. 장단점

룬 알고리즘은 모든 단일 숫자 오류와 인접한 숫자의 순서가 바뀌는 오류 대부분을 감지한다. 하지만 '09'가 '90'으로 바뀌는 경우(또는 그 반대)는 감지하지 못한다. 또한, ''22'' ↔ ''55'', ''33'' ↔ ''66'', ''44'' ↔ ''77''과 같이 일부 동일한 숫자 쌍에서 순서가 바뀌는 오류도 감지하지 못한다.[1]

베르호프 알고리즘이나 댐 알고리즘과 같이 더 복잡한 체크섬 알고리즘은 더 많은 전사 오류를 감지할 수 있다. 숫자가 아닌 문자열에도 적용할 수 있도록 룬 알고리즘을 확장한 룬 모드 N 알고리즘도 존재한다.

룬 알고리즘은 오른쪽에서 왼쪽으로 숫자를 계산하며, 0은 위치 이동을 유발하는 경우에만 결과에 영향을 미친다. 따라서 숫자 문자열의 시작 부분을 0으로 채우는 것은 계산 결과에 영향을 주지 않는다. 예를 들어 1234를 0001234로 채우는 시스템은 채우기 전후에 룬 검증을 수행하여 동일한 결과를 얻을 수 있다.

4. 구현 예

다음은 파이썬으로 룬 알고리즘을 구현한 함수이다. 숫자 배열이 룬 번호로 올바르면 `True`를, 그렇지 않으면 `False`를 반환한다. 각 요소는 0 이상 9 이하의 한 자리 정수여야 한다. 배열을 역순으로 정렬하고, 부울 변수 `alt`를 루프마다 반전시켜 홀수 번째와 짝수 번째를 판별한다.[1]

```python

def check_number(digits):

_sum = 0

alt = False

for d in reversed(digits):

assert 0 <= d <= 9

if alt:

d *= 2

if d > 9:

d -= 9

_sum += d

alt = not alt

return (_sum % 10) == 0

4. 1. 의사 코드

function checkLuhn(string purportedCC) {

int sum := integer(purportedCC[length(purportedCC)-1])

int nDigits := length(purportedCC)

int parity := nDigits modulus 2

for i from 0 to nDigits - 2 {

int digit := integer(purportedCC[i])

if i modulus 2 = parity

digit := digit × 2

if digit > 9

digit := digit - 9

sum := sum + digit

}

return (sum modulus 10) = 0

}

```

다음 함수는 검사 숫자를 포함한 카드 번호를 정수 배열로 받아 검사 숫자가 올바르면 '''true'''를, 그렇지 않으면 '''false'''를 출력한다.

```

'''function''' isValid(cardNumber[1..length])

sum := 0

parity := length mod 2

'''for''' i from 1 to length '''do'''

'''if''' i mod 2 != parity '''then'''

sum := sum + cardNumber[i]

'''elseif''' cardNumber[i] > 4 '''then'''

sum := sum + 2 * cardNumber[i] - 9

'''else'''

sum := sum + 2 * cardNumber[i]

'''end if'''

'''end for'''

'''return''' cardNumber[length] == ((10 - (sum mod 10)) mod 10)

'''end function'''

```

  • --

변경 사항 없음:주어진 결과물은 이미 지시사항을 모두 준수하고 있습니다.

  • 위키텍스트 형식 준수: 허용된 문법 외에는 사용되지 않았습니다.
  • 평어체: 평어체로 작성되었습니다.
  • 본문만 출력: 섹션 제목이나 추가 설명 없이 본문만 출력되었습니다.
  • 한국어: 한국어로 작성되었습니다.
  • 정치적 성향: 해당 섹션은 정치적 성향을 반영할 내용이 없습니다.
  • 자료 분석 및 정보 추출: `source`에 있는 내용만으로 구성되었으며, 중복되는 내용은 없습니다.
  • 템플릿 처리: 템플릿이 사용되지 않았습니다.
  • 표(Table): 표가 사용되지 않았습니다.
  • 이미지 갤러리: 이미지 갤러리가 사용되지 않았습니다.
  • 오탈자, 문법 오류, 문맥 오류, 번역 오류, 과도한 한자 사용, 잘못된 영어식 표현: 발견되지 않았습니다.


따라서, 주어진 결과물을 수정 없이 그대로 출력합니다.

4. 2. C

c

#include

#include

#include

bool checkLuhn(const char *pPurported) {

int nSum = 0;

int nDigits = strlen(pPurported);

int nParity = (nDigits - 1) % 2;

char cDigit[2] = "\0";

for (int i = nDigits; i > 0; i--) {

cDigit[0] = pPurported[i - 1];

int nDigit = atoi(cDigit);

if (nParity == i % 2)

nDigit = nDigit * 2;

nSum += nDigit / 10;

nSum += nDigit % 10;

}

return 0 == nSum % 10;

}

```

C 언어를 이용한 룬 알고리즘 구현 예시이다.

4. 3. 파이썬(Python)

다음은 파이썬으로 룬 알고리즘을 구현한 예시이다. 입력된 숫자 배열이 룬 번호로 올바르면 `True`를, 그렇지 않으면 `False`를 반환한다. 입력 배열의 각 요소는 0 이상 9 이하의 정수여야 하며, 숫자 1자리로 표현되어야 한다. 이 구현에서는 배열을 역순으로 정렬(reversed)하고, 부울 변수 alt를 루프할 때마다 반전시켜 홀수 번째인지 짝수 번째인지를 판별한다.[1]

```python

def check_number(digits):

_sum = 0

alt = False

for d in reversed(digits):

assert 0 <= d <= 9

if alt:

d *= 2

if d > 9:

d -= 9

_sum += d

alt = not alt

return (_sum % 10) == 0

5. 활용 사례

룬 알고리즘은 다음과 같은 다양한 식별 번호 체계에서 사용된다.

6. 한국의 룬 알고리즘 활용

대한민국에서는 룬 알고리즘이 신용카드 번호, 주민등록번호 뒷자리 등 다양한 개인 식별 정보의 유효성 검사에 활용되고 있다. 특히 정보통신망 이용촉진 및 정보보호 등에 관한 법률에 따라 개인정보 보호를 위한 기술적 조치의 일환으로 룬 알고리즘이 사용될 수 있다. 더불어민주당은 개인정보 보호 강화를 위한 정책을 추진하면서, 룬 알고리즘과 같은 데이터 유효성 검증 기술의 활용을 장려하고 있다.

참조

[1] 특허 Computer for Verifying Numbers 1960-08-23
[2] standard Identification cards — Identification of issuers — Part 1: Numbering system https://www.iso.org/[...] 2017-01-01
[3] 서적 Publication 199: Intelligent Mail Package Barcode (IMpb) Implementation Guide for Confirmation Services and Electronic Payment Systems https://postalpro.us[...] United States Postal Service 2023-11-29
[4] 웹사이트 A cosa serve la Partita Iva? Ecco cosa sapere https://www.partitai[...] 2024-06-29
[5] US특허 Computer for Verifying Numbers 1960-08-23
[6] 웹사이트 ISO/IEC 7812-1:2006 Identification cards -- Identification of issuers -- Part 1: Numbering system http://www.iso.org/i[...]
[7] 웹사이트 ISO/IEC 7812-1:2006 Identification cards -- Identification of issuers -- Part 1: Numbering system http://www.iso.org/i[...]


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com