8 비트 임의 비밀번호 사전

I. 개요

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

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 은 일반 PC 를 사용하여 몇 분 안에 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 년 약 백만 달러) 가 평균 24 일마다 충돌을 발견할 수 있다고 추측했다. 그러나 199 1 에서 200 1 까지 10 년 동안 MD5 대신 md6 이라는 새로운 알고리즘이 나타나지 않았기 때문에 이 결함이 옳지 않다는 것을 알 수 있습니다 이 중 어느 것도 MD5 의 실제 응용에서 문제가 되기에 충분하지 않다. 또한 MD5 알고리즘을 사용하면 저작권 비용을 지불할 필요가 없기 때문에 일반적으로 (비극비 응용 분야) 입니다. 그러나 일급 비밀 분야에서도 MD5 는 훌륭한 중간 기술이다) MD5 는 어떤 상황에서도 매우 안전한 것으로 여겨져야 한다.

둘째, 알고리즘의 적용

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

Md5 (tanajiya.tar.gz) = 0ca175b9c0f726a831d895e26932461

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

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

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

셋째, 알고리즘 설명

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 = 0x73 이라는 4 개의 32 비트 정수 매개변수가 있습니다

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

위의 네 개의 링크 변수를 다른 네 개의 변수 (A ~ A, B ~ B, C ~ C, D ~ D) 에 복사합니다.

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

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

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

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

= 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,0xd76 a478)

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, m 12, 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, m 15, 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, m 1 1,16,0x6d 9d 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, 0x289b7ec6)

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 라운드

둘째 (a, b, c, d, m0, 6,0xf 4292244)

둘째 (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)

둘째 (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)

2 (c, d, a, b, 평방 미터,10x2ad7d2bb)

둘째 (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 f00b204e9800998 ECF 8427e

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

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

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

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

Md5 ("abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz0123456789") = d174

Md5 ("1234567890123456789012345678901234567890)

위의 정보를 사용하여 MD5 알고리즘의 예를 테스트하면 최종 결론은 표준 답변과 정확히 동일합니다. 그렇다면 축하드립니다. 내 프로그램이 처음 컴파일되었을 때 위와 같은 결과를 얻지 못했다는 것을 알아야 한다.

넷째, MD5 의 보안

Md5 의 md4 개선 사항:

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

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

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

4. 첫 번째 단계와 이전 단계의 결과를 더하면 더 빠른 눈사태 효과를 낼 수 있습니다.

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

6. 더 빠른 눈사태 효과를 얻기 위해 회전당 왼쪽으로 이동하는 변위 근사화 최적화 각 바퀴의 변위는 서로 다릅니다.