{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# MD5 en Python, d'après le pseudo-code de Wikipedia"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "from struct import  pack, unpack # pour gérer le little-endian\n",
    "from math import sin\n",
    "\n",
    "s = [ 7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,\n",
    "      5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,\n",
    "      4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,\n",
    "      6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21 ]\n",
    "\n",
    "K = [0]*64\n",
    "for i in range(64): K[i] = int(2**32 * abs(sin(i + 1.)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['0xd76aa478', '0xe8c7b756', '0x242070db', '0xc1bdceee', '0xf57c0faf', '0x4787c62a', '0xa8304613', '0xfd469501', '0x698098d8', '0x8b44f7af', '0xffff5bb1', '0x895cd7be', '0x6b901122', '0xfd987193', '0xa679438e', '0x49b40821', '0xf61e2562', '0xc040b340', '0x265e5a51', '0xe9b6c7aa', '0xd62f105d', '0x2441453', '0xd8a1e681', '0xe7d3fbc8', '0x21e1cde6', '0xc33707d6', '0xf4d50d87', '0x455a14ed', '0xa9e3e905', '0xfcefa3f8', '0x676f02d9', '0x8d2a4c8a', '0xfffa3942', '0x8771f681', '0x6d9d6122', '0xfde5380c', '0xa4beea44', '0x4bdecfa9', '0xf6bb4b60', '0xbebfbc70', '0x289b7ec6', '0xeaa127fa', '0xd4ef3085', '0x4881d05', '0xd9d4d039', '0xe6db99e5', '0x1fa27cf8', '0xc4ac5665', '0xf4292244', '0x432aff97', '0xab9423a7', '0xfc93a039', '0x655b59c3', '0x8f0ccc92', '0xffeff47d', '0x85845dd1', '0x6fa87e4f', '0xfe2ce6e0', '0xa3014314', '0x4e0811a1', '0xf7537e82', '0xbd3af235', '0x2ad7d2bb', '0xeb86d391']\n"
     ]
    }
   ],
   "source": [
    "print  ([hex(k) for k in K]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Padding. On doit arriver à un multiple de 512 bits\n",
    "from codecs import *\n",
    "\n",
    "def pad(x):\n",
    "    m = len (x)*8\n",
    "    d = (m%512) - 448 # On concatène un bit 1 suivi de d-1 bits 0\n",
    "    if d<0: d = -d    # pour arriver à un nomnbre congru à 448 modulo 512\n",
    "    else: d = 512 - d\n",
    "    # p = decode('%X' % int('1'+'0'*(d-1),2),'hex') # pour tester\n",
    "    # ou encore a = 1<<(d-1)\n",
    "    # p = a.to_bytes((d//8),'big')\n",
    "    p = decode('%X' % (1<<(d-1)),'hex')\n",
    "    y = x+p\n",
    "    n = pack('<Q',(m % 2**64) ) # les 64 derniers codent m en little-endian \n",
    "    return y+n\n",
    "\n",
    "def split(x):        # On découpe x en blocs de 64 octets = 512 bits\n",
    "    assert len(x) % 64 == 0\n",
    "    return [x[i*64:(i+1)*64] for i in range(len(x)//64)]\n",
    "\n",
    "def leftrotate(x,c): # La fonction définie dans la spécification; calculs modulo 2**32\n",
    "    x &= 0xffffffff\n",
    "    return  (x <<c ) | (x >>(32-c)) & 0xffffffff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def  md5sum(x):\n",
    "    a0 = 0x67452301   #A\n",
    "    b0 = 0xefcdab89   #B\n",
    "    c0 = 0x98badcfe   #C\n",
    "    d0 = 0x10325476   #D\n",
    "\n",
    "    y = pad(x)\n",
    " \n",
    "    chunks = split(y)\n",
    "    for chunk in chunks:\n",
    "        M = unpack('<16I',chunk) # On décode en 16 \"unsigned int\", little-endian\n",
    "        A,B,C,D = a0,b0,c0,d0\n",
    "        for i in range(64):\n",
    "            if i in range(16):\n",
    "                F = (B&C) | ((~B)&D)\n",
    "                g = i\n",
    "            elif i in range(16,32):\n",
    "                F = (D&B) | ((~D)&C)\n",
    "                g = (5*i+1) % 16\n",
    "            elif i in range(32,48):\n",
    "                F = B^C^D\n",
    "                g = (3*i+5) % 16\n",
    "            else:\n",
    "                F = C^(B|(~D))\n",
    "                g = (7*i) % 16\n",
    "            dTemp = D\n",
    "            D = C\n",
    "            C = B\n",
    "            B = (B + leftrotate((A + F + K[i] + M[g]), s[i])) & 0xffffffff\n",
    "            A = dTemp\n",
    "        a0 = (a0+A)  & 0xffffffff\n",
    "        b0 = (b0+B)  & 0xffffffff\n",
    "        c0 = (c0+C)  & 0xffffffff\n",
    "        d0 = (d0+D)  & 0xffffffff\n",
    "    digest = (a0,b0,c0,d0)\n",
    "  #  print(a0,b0,c0,d0)\n",
    "    return encode(pack('<4I',*digest),'hex')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b'd41d8cd98f00b204e9800998ecf8427e'"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "md5sum(b'')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'d41d8cd98f00b204e9800998ecf8427e'"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from hashlib import md5\n",
    "md5(b'').hexdigest()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b'534d72625c1975d7bd66885ed7238c29'\n",
      "534d72625c1975d7bd66885ed7238c29\n"
     ]
    }
   ],
   "source": [
    "print (md5sum(b'abracadabra'*666))\n",
    "print (md5(b'abracadabra'*666).hexdigest())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b'\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x80\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00@\\x00\\x00\\x00\\x00\\x00\\x00\\x00'"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pad(b'\\x00'*8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0b1000000'"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bin(ord('@'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b'AAAAAAAA\\x80\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00@\\x00\\x00\\x00\\x00\\x00\\x00\\x00'"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pad(b'AAAAAAAA')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "128"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "int('10000000',2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0x80'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hex(_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}