Я изучаю курс по криптографии и застрял на задании. Инструкции следующие:
Открытый текст plain6.txt был зашифрован с помощью DES для encrypt6.dat с использованием 64-битного ключа, заданного в виде строки из 8 символов (64 биты, из которых каждый 8-й бит игнорируется), все символы являются буквами (нижний или верхний регистр) и цифры (от 0 до 9).
Чтобы выполнить задание, пришлите мне ключ шифрования до февраля. 12, 23,59.
Примечание: я ожидаю получить 8-байтовый (64-битный) ключ. Каждый байт должен совпадают с соответствующим байтом в моем ключе, за исключением наименьшего значащий бит, который не используется в DES и, следовательно, может быть произвольным.
Вот код моей первой попытки в Python:
import time
from Crypto.Cipher import DES
class BreakDES(object):
def __init__(self, file, passwordLength = 8, testLength = 8):
self.file = file
self.passwordLength = passwordLength
self.testLength = testLength
self.EncryptedFile = open(file + '.des')
self.DecryptedFile = open(file + '.txt')
self.encryptedChunk = self.EncryptedFile.read(self.testLength)
self.decryptedChunk = self.DecryptedFile.read(self.testLength)
self.start = time.time()
self.counter = 0
self.chars = range(48, 58) + range(65, 91) + range(97, 123)
self.key = False
self.broken = False
self.testPasswords(passwordLength, 0, '')
if not self.broken:
print "Password not found."
duration = time.time() - self.start
print "Brute force took %.2f" % duration
print "Tested %.2f per second" % (self.counter / duration)
def decrypt(self):
des = DES.new(self.key.decode('hex'))
if des.decrypt(self.encryptedChunk) == self.decryptedChunk:
self.broken = True
print "Password found: 0x%s" % self.key
self.counter += 1
def testPasswords(self, width, position, baseString):
for char in self.chars:
if(not self.broken):
if position < width:
self.testPasswords(width, position + 1, baseString + "%c" % char)
self.key = (baseString + "%c" % char).encode('hex').zfill(16)
self.decrypt()
# run it for password length 4
BreakDES("test3", 4)
Я получаю скорость 60 000 попыток в секунду. Пароль из 8 байтов и 62 символов дает 13 триллионов возможностей, а это значит, что при такой скорости мне потребуется 130 лет, чтобы разгадать пароль. Я знаю, что это неэффективная реализация и что я мог бы получить более высокую скорость на более быстром языке, таком как C или его разновидности, но я никогда не программировал на них. Даже если я получу ускорение на 10, мы все равно сделаем огромный скачок от 10 000 000 000 в секунду к диапазону часов.
Что мне не хватает? Предполагается, что это слабый ключ :). Что ж, слабее, чем полный набор из 256 символов.
РЕДАКТИРОВАТЬ
Из-за некоторой двусмысленности в назначении, вот полное описание и некоторые тестовые файлы для калибровки: http://users.abo.fi/ipetre/crypto/assignment6.html
РЕДАКТИРОВАТЬ 2
Это грубая реализация C, которая получает около 2.000.000 паролей / с на ядро на i7 2600K. Вы должны указать первый символ пароля и можете вручную запустить несколько экземпляров на разных ядрах / компьютерах. С его помощью мне удалось решить проблему за пару часов на четырех компьютерах.
#include /* fprintf */
#include /* malloc, free, exit */
#include
#include /* strerror */
#include
#include
static long long unsigned nrkeys = 0; // performance counter
char *
Encrypt( char *Key, char *Msg, int size)
{
static char* Res;
free(Res);
int n=0;
DES_cblock Key2;
DES_key_schedule schedule;
Res = ( char * ) malloc( size );
/* Prepare the key for use with DES_ecb_encrypt */
memcpy( Key2, Key,8);
DES_set_odd_parity( &Key2 );
DES_set_key_checked( &Key2, &schedule );
/* Encryption occurs here */
DES_ecb_encrypt( ( unsigned char (*) [8] ) Msg, ( unsigned char (*) [8] ) Res,
&schedule, DES_ENCRYPT );
return (Res);
}
char *
Decrypt( char *Key, char *Msg, int size)
{
static char* Res;
free(Res);
int n=0;
DES_cblock Key2;
DES_key_schedule schedule;
Res = ( char * ) malloc( size );
/* Prepare the key for use with DES_ecb_encrypt */
memcpy( Key2, Key,8);
DES_set_odd_parity( &Key2 );
DES_set_key_checked( &Key2, &schedule );
/* Decryption occurs here */
DES_ecb_encrypt( ( unsigned char (*) [8]) Msg, ( unsigned char (*) [8]) Res,
&schedule, DES_DECRYPT );
return (Res);
}
void ex_program(int sig);
int main(int argc, char *argv[])
{
(void) signal(SIGINT, ex_program);
if ( argc != 4 ) /* argc should be 2 for correct execution */
{
printf( "Usage: %s ciphertext plaintext keyspace \n", argv[0] );
exit(1);
}
FILE *f, *g;
int counter, i, prime = 0, len = 8;
char cbuff[8], mbuff[8];
char letters[] = "02468ACEGIKMOQSUWYacegikmoqsuwy";
int nbletters = sizeof(letters)-1;
int entry[len];
char *password, *decrypted, *plain;
if(atoi(argv[3]) > nbletters-2) {
printf("The range must be between 0-%d\n", nbletters-2);
exit(1);
}
prime = atoi(argv[1])
// read first 8 bytes of the encrypted file
f = fopen(argv[1], "rb");
if(!f) {
printf("Unable to open the file\n");
return 1;
}
for (counter = 0; counter < 8; counter ++) cbuff[counter] = fgetc(f);
fclose(f);
// read first 8 bytes of the plaintext file
g = fopen(argv[2], "r");
if(!f) {
printf("Unable to open the file\n");
return 1;
}
for (counter = 0; counter < 8; counter ++) mbuff[counter] = fgetc(g);
fclose(g);
plain = malloc(8);
memcpy(plain, mbuff, 8);
// fill the keys
for(i=0 ; i