사전에서 id 생성

I. 개요

MD5 의 전체 이름은 message-digest algorithm 5 로, MIT 컴퓨터과학연구소와 RSA 데이터안전사의 Ronald L. rivest 가 1990 년대 초에 개발한 것으로 MD2, md3, md4 가 개발했습니다. 디지털 서명 소프트웨어를 사용하여 개인 키에 서명하기 전에 대용량 정보를 안전한 형식 (즉, 모든 길이의 바이트 문자열을 일정한 길이의 큰 정수로 변환) 으로' 압축' 하는 역할을 합니다. Md2, md4, MD5 모두 임의 길이의 정보를 얻고 128 비트 정보 요약을 생성해야 합니다. 이러한 알고리즘의 구조는 다소 비슷하지만 MD2 는 md4 및 MD5 와 완전히 다릅니다. MD2 는 8 비트 컴퓨터에 최적화된 반면 md4 및 MD5 는 32 비트 컴퓨터에 맞게 설계되었기 때문입니다. 인터넷 rfcs1321(http://www.ietf.org/RFC/RFC1

Rivest 는 1989 에서 MD2 알고리즘을 개발했습니다. 이 알고리즘에서는 먼저 데이터를 사용하여 정보를 보충하여 정보의 바이트 길이가 16 의 배수가 되도록 합니다. 그런 다음 16 비트 체크섬이 메시지 끝에 추가됩니다. 새로 생성된 정보를 기반으로 해시 값을 계산합니다. 나중에 rogier 와 chauvaud 는 체크섬을 무시하면 MD2 충돌이 발생한다는 것을 발견했습니다. Md2 알고리즘의 암호화 결과는 고유합니다. 중복이 없습니다.

Rivest 는 알고리즘의 보안을 강화하기 위해 1990 에서 md4 알고리즘을 개발했습니다. Md4 알고리즘은 또한 정보의 바이트 길이가 448 을 더한 후 5 12 로 나눌 수 있도록 정보를 채워야 합니다 (정보 바이트 길이 mod 5 12 = 448). 그런 다음 64 비트 바이너리 메시지의 초기 길이를 추가합니다. 정보를 5 12 비트 damg 으로 처리합니까? Rd/merkle 반복 구조의 블록으로, 각 블록은 세 가지 단계를 거칩니다. Den Boer, bosselaers 및 기타 사람들은 md4 버전의 1 단계와 3 단계를 공격하는 취약점을 빠르게 발견했습니다. Dobbertin 은 일반 개인용 컴퓨터를 사용하여 몇 분 안에 md4 정식 버전의 충돌을 찾는 방법을 보여 줍니다. 이 충돌은 실제로 다른 콘텐츠를 암호화하지만 동일한 암호화 결과를 얻을 수 있는 취약점입니다. Md4 가 제거되었다는 것은 의심의 여지가 없습니다.

Md4 알고리즘의 보안에는 이렇게 큰 취약점이 있지만, 나중에 개발된 몇 가지 정보 보안 암호화 알고리즘의 출현에 중요한 지침 역할을 합니다. Md5 외에도 sha- 1, ripe-md, 하버드 등이 있습니다.

1 년 후, 199 1 년, rivest 는 기술적으로 더 성숙한 MD5 알고리즘을 개발했습니다. Md4 를 기반으로 "안전벨트" 라는 개념을 추가했습니다. Md5 는 md4 보다 약간 느리지만 더 안전합니다. 이 알고리즘은 md4 설계와 약간 다른 네 단계로 구성되어 있습니다. Md5 알고리즘에서 정보 다이제스트의 크기와 채우기에 필요한 조건은 md4 와 동일합니다. Den Boer 와 bosselaers 는 MD5 알고리즘에서 유사 충돌을 발견했지만 다른 암호화된 결과는 발견되지 않았습니다.

Van oorschot 과 wiener 는 해시의 충돌을 검색하는 강력한 해시 함수를 고려해 본 바 있으며, MD5 충돌 검색만을 전문으로 하는 시스템 (1994 년 약 100 만 달러) 이 평균 24 일마다 발견될 것으로 추정하고 있다 하지만 199 1 에서 200 1 까지 10 년 동안 MD5 대신 md6 이라는 새 알고리즘이 나타나지 않았기 때문에 우리는 다음을 수행할 수 있습니다 Md5 의 실제 응용에서는 이 모든 것이 문제가 되기에 충분하지 않다. 또한 MD5 알고리즘을 사용하면 저작권 비용을 지불할 필요가 없기 때문에 일반적으로 (비극비 응용 분야) 입니다. 그러나 극비 분야에서도 MD5 는 우수한 중간 기술이다.) 어쨌든 MD5 는 매우 안전한 것으로 여겨져야 한다.

둘째, 알고리즘의 적용

Md5 의 일반적인 응용 프로그램은 메시지가 변조되지 않도록 메시지에 대한 메시지 요약을 생성하는 것입니다. 예를 들어, UNIX 의 경우 많은 소프트웨어는 파일 이름이 같고 파일 확장명이 입니다. Md5 의 파일입니다. 이 파일에서는 보통 한 줄의 텍스트만 있는데, 일반적인 구조는 다음과 같습니다.

Md5 (tanajiya.tar.gz) = 0ca175b9 c0f726a831d895e26932461

이것은 tanajiya.tar.gz 문서의 디지털 서명입니다. Md5 는 전체 파일을 하나의 큰 텍스트 메시지로 간주하고 되돌릴 수 없는 문자열 변환 알고리즘을 통해 이 고유한 MD5 메시지 요약을 생성합니다. 향후 이 파일을 전파하는 과정에서 파일의 내용 변경 사항 (인위적인 수정이나 다운로드 시 회선 불안정으로 인한 전송 오류 등) 에 관계없이 ), 이 파일의 MD5 를 다시 계산하면 정보 요약이 다르다는 것을 알 수 있습니다. 잘못된 파일일 뿐입니다. 제 3 자 인증 기관이 있는 경우 MD5 는 문서 작성자의 "거부", 즉 디지털 서명 애플리케이션도 방지합니다.

Md5 는 암호화 및 암호 해독 기술에도 널리 사용됩니다. 예를 들어, UNIX 시스템에서 사용자의 암호는 MD5 (또는 기타 유사한 계산 방법) 를 통해 암호화되어 파일 시스템에 저장됩니다. 사용자가 로그인하면 사용자가 입력한 비밀번호가 MD5 값으로 계산되고 파일 시스템에 저장된 MD5 값과 비교되어 정확한 비밀번호를 입력했는지 확인합니다. 이러한 단계를 통해 시스템은 사용자 암호의 명확한 코드를 모르는 상태에서 사용자 로그인 시스템의 합법성을 확인할 수 있습니다. 이를 통해 시스템 관리자 권한을 가진 사용자가 사용자의 비밀번호를 알 수 없을 뿐만 아니라 비밀번호 해독의 난이도를 어느 정도 높일 수 있습니다.

바로 이런 이유로 해커가 비밀번호를 해독하는 가장 일반적인 방법 중 하나는' 윤사전' 이라는 방법이다. 사전을 가져오는 방법에는 두 가지가 있습니다. 하나는 매일 수집한 암호로 사용되는 문자열 테이블이고, 다른 하나는 조합 방법을 정렬하여 생성된 것입니다. 먼저 MD5 프로그램을 통해 이러한 사전 항목의 MD5 값을 계산한 다음 해당 사전에서 대상의 MD5 값을 검색합니다. 암호의 최대 길이가 8 바이트이고 암호는 문자와 숫자일 수 있다고 가정합니다. ***26+26+ 10=62 자, 사전의 항목 수는 p(62,1)+ 이 암호화 기술은 유닉스 시스템에서 널리 사용되고 있으며, 이는 유닉스 시스템이 일반 운영 체제보다 더 강력한 이유이기도 하다.

셋째, 알고리즘 설명

Md5 알고리즘에 대한 간단한 설명은 다음과 같습니다. MD5 는 5 12 비트 패킷의 입력 정보를 처리하며 각 패킷은 16 개의 32 비트 패킷으로 나뉩니다. 일련의 처리 후 알고리즘의 출력은 4 개의 32 비트 패킷으로 구성되며 4 개의 32 비트 패킷을 연결하여 128 비트 해시를 생성합니다.

Md5 알고리즘에서는 먼저 5 12 바이트 길이의 결과가 448 이 되도록 정보를 채워야 합니다. 따라서 정보의 비트 길이는 n*5 12+448, 즉 n*64+56 바이트로 확장됩니다. 여기서 N 은 양의 정수입니다. 정보 뒤에 1 과 무수한 0 을 채우고 위 조건이 충족될 때까지 0 으로 정보를 채우는 것을 중지하지 마십시오. 그런 다음 결과 뒤에 64 비트 이진수로 표시된 미리 채워진 정보 길이를 추가합니다. 이 두 단계를 거쳐 현재 정보자 길이 = n * 5 12+448+64 = (n+1) * 512; 이렇게 하는 이유는 사후 처리에서 정보 길이에 대한 요구 사항을 충족하기 위해서입니다.

Md5 에는 a=0x0 1234567, b=0x89abcdef, c = 0xxfedcba98, d = 0x765432 인 링크 변수라는 4 개의 32 비트 정수 매개변수가 있습니다

이 네 개의 링크 변수가 설정되면 알고리즘이 4 륜 루프 작업을 시작합니다. 주기 수는 정보의 5 12 비트 패킷 수입니다.

위의 네 개의 링크 변수를 다른 네 개의 변수 (a ~ a, b ~ b, c ~ c, d ~ d) 에 복사합니다.

4 개의 주요 주기 (md4 는 3 개) 가 있으며, 각 주기는 매우 유사합니다. 1 라운드 16 조작. A, B, C, D 중 3 개를 비선형 함수 연산한 다음 네 번째 변수, 텍스트의 하위 그룹 및 상수를 결과에 추가합니다. 그런 다음 결과를 오른쪽으로 무한대로 이동하고 a, b, c 또는 d 중 하나를 추가합니다. 마지막으로 a, b, c 또는 d 중 하나를 결과로 바꿉니다.

각 작업에 사용되는 4 개의 비선형 함수 (라운드당 1 개) 를 살펴보겠습니다.

F(x, y, z) = (x & Y) | ((x) & Z)

G(x, y, z) = (x & ampz) | (y & (~z)

H(x, y, z) = x y Z.

I (x, y, z) = y (x | (~ z)

(& 예 및 | 예 또는 ~ 예 또는 아니오, 다름 또는)

이 네 가지 함수의 해석: X, Y 및 Z 의 해당 비트가 독립적이고 통일된 경우 결과의 각 비트도 독립적이고 통일되어야 합니다.

F 는 비트 연산의 함수입니다. 즉, x, y, 그렇지 않으면 Z. 함수 h 는 비트 패리티 연산자입니다.

Mj 가 메시지의 j 번째 하위 그룹 (0 부터 15 까지) 을 나타낸다고 가정합니다.

& lt& ltff(a, b, c, d, mj, s, ti) 는 a = b+((a+(f(b, c, d)+mj+ti+를 나타냅니다

& lt& ltgg(a, b, c, d, mj, s, ti) 는 a = b+((a+(g(b, c, d)+mj+ti+를 나타냅니다

& lt& lthh(a, b, c, d, mj, s, ti) 는 a = b+((a+(h(b, c, d)+mj+ti+를 나타냅니다

& lt& ltii(a, b, c, d, mj, s, ti) 는 a = b+((a+(I(b, c, d)+mj+ti+를 나타냅니다

& lt& lt 이 4 륜 (64 단계) 은 다음과 같습니다.

1 라운드

Ff(a, b, c, d, m0, 7, m0,7,0xd76aa478)

Ff(d, a, b, c, m 1,10xe8c7b756)

Ff(c, d, a, b, m2,10x242070db)

Ff(b, c, d, a, m3, 22,0xc1bdceee)

Ff(a, b, c, d, M4, 0xf57c0faf)

Ff(d, a, b, c, M5,10x4787c62a)

Ff(c, d, a, b, M6,17,0xa8304613)

Ff(b, c, d, a, M7, 22,0x FD 469501)

Ff(a, b, c, d, M8, 0x698098d8)

Ff(d, a, b, c, M9,10x8b44f7af)

Ff(c, d, a, b, m 10, 17, 0xfff 5bb1)

Ff(b, c, d, a, m 1 1, 0x895cd7be)

Ff(a, b, c, d, m12,7,0x6b901122)

Ff(d, a, b, c, m 13,12,0x FD 987193)

Ff(c, d, a, b, m 14,10xa679438e)

Ff(b, c, d, a, m15,22,0x49b40821)

2 라운드

Gg(a, b, c, d, m 1, 5,0xf61e2562)

Gg(d, a, b, c, M6, 9, 0xc040b340)

Gg(c, d, a, b, m 1 1,14,0x265e5a51

Gg(b, c, d, a, m0, 20,0xe9b6 c 7a)

Gg(a, b, c, d, M5, 5,0xd62f105d)

Gg(d, a, b, c, m 10, 9,0x02441453)

Gg(c, d, a, b, m 15,14,0xd8a1e68/kloc-0)

Gg(b, c, d, a, M4, 20,0xe7d 3f bc8)

Gg(a, b, c, d, M9, 5,0x21e1cde6)

Gg(d, a, b, c, m 14, 0xc33707d6)

Gg(c, d, a, b, m3,10xf4d50d87)

Gg(b, c, d, a, M8, 20,0x455a14ed)

Gg(a, b, c, d, m 13, 0xa9e3e905)

Gg(d, a, b, c, m2, 9, 0xfcefa3f8)

Gg(c, d, a, b, M7,10x676f02d9)

Gg(b, c, d, a, m 12, 20,0x8d2 a4 c8a)

3 라운드

Hh(a, b, c, d, M5, 4,0x 0xfffa3942)

Hh(d, a, b, c, M8, 1 1, 0x877 1f68 1)

Hh(c, d, a, b, m116,0x6 d 9 d 6122)

Hh(b, c, d, a, m 14, 23, 0xfde5380c)

Hh(a, b, c, d, m 1, 0xa4beea44)

Hh(d, a, b, c, M4, 1 1, 0x4bdecfa9)

Hh(c, d, a, b, M7,10xf6bb4b60)

Hh(b, c, d, a, m 10, 23,0xbe FBC 70)

Hh(a, b, c, d, m 13, 4,0x289 b7c6)

Hh(d, a, b, c, m0, 1 1, 0xeaa 127fa)

Hh(c, d, a, b, m3,10xd4ef3085)

Hh(b, c, d, a, M6, 23,0x04881d05)

Hh(a, b, c, d, M9, 4,0x d 9 d 4d 039)

Hh(d, a, b, c, m 12, 1 1, 0xe6db99e5)

Hh(c, d, a, b, m 15,16,0x1fa27cf8)

Hh(b, c, d, a, m2, 23,0xc4 ac5665)

4 라운드

Ii(a, b, c, d, m0, 6,0xf 429244)

둘째 (d, a, b, c, M7,10,0x432af97)

둘째 (c, d, a, b, m 14, 15, 0xab9423a7)

둘째 (b, c, d, a, M5, 2 1, 0xfc93a039)

둘째 (a, b, c, d, m 12, 0x655b59c3)

둘째 (d, a, b, c, m3,10,0x8f 0 CCC 92)

둘째 (c, d, a, b, m 10, 15, 0xffeff47d)

Ii(b, c, d, a, m 1, 2 1, 0x85845dd 1)

둘째 (a, b, c, d, M8, 6, 0x6fa87e4f)

둘째 (d, a, b, c, m 15, 10, 0xfe2ce6e0)

둘째 (c, d, a, b, M6,15,0xa3014314)

둘째 (b, c, d, a, m 13, 2 1, 0x4e0811a

둘째 (a, b, c, d, M4, 6, 0xf7537e82)

2 (d, a, b, c, m 1 1, 10, 0xbd3af235)

Ii(c, d, a, b, m2,10x2ad7d2bb)

Ii(b, c, d, a, M9, 2 1, 0xeb86d39 1)

상수 ti 는 다음과 같이 선택할 수 있습니다.

I 단계에서 ti 는 4294967296 * ABS(sin(I)) 의 정수 부분이고 I 의 단위는 라디안입니다. (4294967296 은 2 의 32 제곱이다)

이 모든 것이 완료되면 각각 a, b, c, d 를 추가합니다. 그런 다음 다음 패킷에 대해 이 알고리즘을 계속 실행합니다. 최종 출력은 a, b, c, d 의 캐스케이드입니다 .....

앞서 언급한 방법에 따라 MD5 알고리즘을 구현할 경우 다음 정보를 사용하여 프로그램에 오류가 있는지 쉽게 테스트할 수 있습니다.

Md5 ("") = D41D8 CD 98 f00b 204e 9800998 ECF 8427e

Md5 ("a") = 0cc175b9c0f1b6a831c399e2697266/kloc-0

Md5 ("ABC") = 900150983 CD 24 fb0d 6963f 7d 28e17f72

Md5 ("메시지 요약") = f96b697d7cb7938d525a2f31AAF161d0

Md5 ("abcdefghijklmnopqrstuvwxyz") = C3 fcd 3d 76192 e4007 DFB 496 CCA 67e13b

Md5 ("abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz0123456789") = d174

Md5 ("1234567890123456789012345678901234567890"

위의 정보를 사용하여 MD5 알고리즘의 예를 테스트하고 최종 결론이 표준 답변과 정확히 일치하는 경우 축하드립니다. 너도 알다시피, 내 프로그램이 처음 컴파일되었을 때 위와 같은 결과를 얻지 못했다.

넷째, MD5 의 보안

Md5 의 md4 개선 사항:

1. 네 번째 라운드를 추가했습니다.

각 단계에는 고유한 인상 상수가 있습니다.

3. 2 라운드에서 함수 G 의 대칭성을 약화시키기 위해 함수 G 는 (x &；; Y) | (x & Z) | (y & Z) 가 (x &；; Z) | (y & (~ z);

4. 첫 번째 단계는 이전 단계의 결과를 더합니다. 이로 인해 더 빠른 눈사태 효과가 발생합니다.

5. 2 차 및 3 차 방문 메시지 하위 패키지 순서를 변경하여 더욱 다르게 만듭니다.

6. 매 라운드마다 왼쪽으로 이동하는 변위는 더 빠른 눈사태 효과를 위해 대략적으로 최적화됩니다. 각 바퀴의 변위는 서로 다르다.