Криптография на Python: шифрование информации и создание электронных цифровых подписей с помощью пак
- вторник, 25 августа 2015 г. в 02:11:15
python
http://habrahabr.ru/post/265309/
Долго мучился с PyCrypto, в итоге получилась эта статья и полная реализация следующего протокола:
Этап отправки:
1. Алиса подписывает сообщение своей цифровой подписью и шифрует ее открытым ключом Боба (асимметричным алгоритмом).
2. Алиса генерирует случайный сеансовый ключ и шифрует этим ключом сообщение (с помощью симметричного алгоритма).
3. Сеансовый ключ шифруется открытым ключом Боба (асимметричным алгоритмом).
Алиса посылает Бобу зашифрованное сообщение, подпись и зашифрованный сеансовый ключ.
Этап приёма:
Боб получает зашифрованное сообщение Алисы, подпись и зашифрованный сеансовый ключ.
4. Боб расшифровывает сеансовый ключ своим закрытым ключом.
5. При помощи полученного, таким образом, сеансового ключа Боб расшифровывает зашифрованное сообщение Алисы.
6. Боб расшифровывает и проверяет подпись Алисы.
Вышеописанный протокол является гибридной системой шифрования, которая работают следующим образом. Для симметричного алгоритма AES (или любого другого) генерируется случайный сеансовый ключ.
Такой ключ как правило имеет размер от 128 до 512 бит (в зависимости от алгоритма). Затем используется симметричный алгоритм для шифрования сообщения. В случае блочного шифрования необходимо использовать режим шифрования (например CBC), что позволит шифровать сообщение с длиной, превышающей длину блока. Что касается самого случайного ключа, он должен быть зашифрован с помощью открытого ключа получателя сообщения, и именно на этом этапе применяется криптосистема с открытым ключом RSA.
Поскольку сеансовый ключ короткий, его шифрование занимает немного времени. Шифрование набора сообщений с помощью асимметричного алгоритма — это задача вычислительно более сложная, поэтому здесь предпочтительнее использовать симметричное шифрование. Затем достаточно отправить сообщение, зашифрованное симметричным алгоритмом, а также соответствующий ключ в зашифрованном виде. Получатель сначала расшифровывает ключ с помощью своего секретного ключа, а затем с помощью полученного ключа получает и всё сообщение.
Начнем с генерации пары ключей для Алисы и Боба.
На данный момент система шифрования на основе RSA считается надёжной, начиная с размера n в 2048 бит.
В системе RSA можно создавать сообщения, которые будут и зашифрованы, и содержать цифровую подпись. Для этого автор сначала должен добавить к сообщению свою цифровую подпись, а затем — зашифровать получившуюся в результате пару (состоящую из самого сообщения и подписи к нему) с помощью открытого ключа, принадлежащего получателю. Получатель расшифровывает полученное сообщение с помощью своего секретного ключа и проверяет подпись автора с помощью его открытого ключа.
Использование односторонней криптографической хеш-функции позволяет оптимизировать вышеописанный алгоритм цифровой подписи. Производится шифрование не самого сообщения, а значения хеш-функции, взятой от сообщения. Данный метод обеспечивает следующие преимущества:
1. Понижение вычислительной сложности. Как правило, документ значительно больше его хеша.
2. Повышение криптостойкости. Криптоаналитик не может, используя открытый ключ, подобрать подпись под сообщение, а только под его хеш.
3. Обеспечение совместимости. Большинство алгоритмов оперирует со строками бит данных, но некоторые используют другие представления. Хеш-функцию можно использовать для преобразования произвольного входного текста в подходящий формат.
Хэш-функции, представляют собой функции, математические или иные, которые получают на вход строку переменной длинны (называемую прообразом) и преобразуют ее в строку фиксированной, обычно меньшей, длинны (называемую значением хэш-функции). Смысл хэш-функции состоит в получении характерного признака прообраза — значения, по которому анализируются различные прообразы при решении обратной задачи. Однонаправленная хэш-функция — это хэш-функция, которая работает только в одном направлении: легко вычислить значение хэш-функции по прообразу, но трудно создать прообраз, значение хэш-функции которого равно заданной величине. Хэш-функция является открытой, тайны ее расчета не существует. Безопасность однонаправленной хэш-функции заключается именно в ее однонаправленности.
Однонаправленная функция H(M) применяется к сообщению произвольной длины М и возвращает значение фиксированной длинны h.
h = H(M), где h имеет длину m
Многие функции позволяют вычислить значение фиксированной длинны по входным данным произвольной длинны, но у однонаправленной хэш-функции есть дополнительные свойства, делающие их однонаправленными:
Зная М, легко вычислить h
Зная H, трудно определить М, для которого H(M) = h
Зная М, трудно определить другое сообщение, М', для которого H(M) = H(M')
Переходим к написанию первого пункта протокола:
1. Алиса подписывает сообщение своей цифровой подписью и шифрует ее открытым ключом Боба (асимметричным алгоритмом).
Количество байт в подписи должно быть кратно 16, иначе при шифровании асимметричным алгоритмом выдаст ошибку. Я добавил блок check long signature, который добавляет в подпись недостающее число байт и записывает это число в конец подписи. Перед проверкой подписи нужно удалить все эти символы. При шифровании каждый блок по 16 байт шифруется отдельно, для этого я использовал цикл. При генерации случайного числа (генератором псевдослучайных чисел) для шифра AES (переменная randomnum) в методе read обязательно указывайте длину кратную 128 бит или 16 байт.
Я использовал 128-битный алгоритм хеширования MD5.
В следующем листинге код для двух пунктов протокола:
2. Алиса генерирует случайный сеансовый ключ и шифрует этим ключом сообщение (с помощью симметричного алгоритма).
3. Сеансовый ключ шифруется открытым ключом Боба (асимметричным алгоритмом).
Количество байт в сообщении должно быть кратно 16. Как и в случае с подписью я изменил исходное сообщение, затем создал сессионный ключ размером 256 бит. Ну и конечно зашифровал сессионный ключ с помощью открытого ключа Боба.
для режима CBC требуется вектор инициализации (IV) (переменная iv).
В криптографии, вектор инициализации (IV) представляет собой некоторое число, как правило оно должно быть случайным или псевдослучайным. Случайность имеет решающее значение для достижения семантической безопасности, которая при повторном использовании схемы под тем же ключом не позволит злоумышленнику вывести отношения между сегментами зашифрованных сообщений. Вектор инициализации не шифруется и сохраняется перед зашифрованным сообщением.
Далее Алиса посылает Бобу зашифрованное сообщение, подпись и зашифрованный сеансовый ключ.
Боб получает зашифрованное сообщение Алисы, подпись и зашифрованный сеансовый ключ.
4. Боб расшифровывает сеансовый ключ своим закрытым ключом.
5. При помощи полученного, таким образом, сеансового ключа Боб расшифровывает зашифрованное сообщение Алисы.
Для дешифрования не забывайте получить вектор инициализации, который находится в первых 16 байтах шифротекста.
В блоке remove unnecessary мы удаляем уже ненужные символы, которые мы добавляли в сообщение для его шифрования (дина сообщения должна быть кратна 16).
Последний и самый трудный этап:
6. Боб расшифровывает и проверяет подпись Алисы.
Каждые 16 байт подписи зашифровывались в 256 байт шифротекста, поэтому подпись дешифруется блоками по 256 байт. Подпись это кортеж, поэтому строку signature нужно обязательно преобразовать в кортеж. После проверки подписи, в конец файла signature.txt добавится True — в случае успешной проверки или False если сообщение после подписания было изменено.
Безопасность RSA основана на сложности задачи факторизации произведения двух больших простых чисел. Факторизация целых чисел для больших чисел является задачей большой сложности. Не существует никакого известного способа, чтобы решить эту задачу быстро. Факторизация кандидат в односторонние функции, которые относительно легко вычисляются, но инвертируются с большим трудом. То есть, зная x просто рассчитать f(x), но по известному f(x) нелегко вычислить x. Здесь, «нелегко» означает, что для вычисления x по f(x) могут потребоваться миллионы лет, даже если над этой проблемой будут биться все компьютеры мира.
Литература:
Брюс Шнайер — Прикладная криптография
Долго мучился с PyCrypto, в итоге получилась эта статья и полная реализация следующего протокола:
Этап отправки:
1. Алиса подписывает сообщение своей цифровой подписью и шифрует ее открытым ключом Боба (асимметричным алгоритмом).
2. Алиса генерирует случайный сеансовый ключ и шифрует этим ключом сообщение (с помощью симметричного алгоритма).
3. Сеансовый ключ шифруется открытым ключом Боба (асимметричным алгоритмом).
Алиса посылает Бобу зашифрованное сообщение, подпись и зашифрованный сеансовый ключ.
Этап приёма:
Боб получает зашифрованное сообщение Алисы, подпись и зашифрованный сеансовый ключ.
4. Боб расшифровывает сеансовый ключ своим закрытым ключом.
5. При помощи полученного, таким образом, сеансового ключа Боб расшифровывает зашифрованное сообщение Алисы.
6. Боб расшифровывает и проверяет подпись Алисы.
Вышеописанный протокол является гибридной системой шифрования, которая работают следующим образом. Для симметричного алгоритма AES (или любого другого) генерируется случайный сеансовый ключ.
Такой ключ как правило имеет размер от 128 до 512 бит (в зависимости от алгоритма). Затем используется симметричный алгоритм для шифрования сообщения. В случае блочного шифрования необходимо использовать режим шифрования (например CBC), что позволит шифровать сообщение с длиной, превышающей длину блока. Что касается самого случайного ключа, он должен быть зашифрован с помощью открытого ключа получателя сообщения, и именно на этом этапе применяется криптосистема с открытым ключом RSA.
Поскольку сеансовый ключ короткий, его шифрование занимает немного времени. Шифрование набора сообщений с помощью асимметричного алгоритма — это задача вычислительно более сложная, поэтому здесь предпочтительнее использовать симметричное шифрование. Затем достаточно отправить сообщение, зашифрованное симметричным алгоритмом, а также соответствующий ключ в зашифрованном виде. Получатель сначала расшифровывает ключ с помощью своего секретного ключа, а затем с помощью полученного ключа получает и всё сообщение.
Начнем с генерации пары ключей для Алисы и Боба.
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
# key generation
privatekey = RSA.generate(2048)
f = open('c:\cipher\\alisaprivatekey.txt','wb')
f.write(bytes(privatekey.exportKey('PEM'))); f.close()
publickey = privatekey.publickey()
f = open('c:\cipher\\alisapublickey.txt','wb')
f.write(bytes(publickey.exportKey('PEM'))); f.close()
privatekey = RSA.generate(2048)
f = open('c:\cipher\\bobprivatekey.txt','wb')
f.write(bytes(privatekey.exportKey('PEM'))); f.close()
publickey = privatekey.publickey()
f = open('c:\cipher\\bobpublickey.txt','wb')
f.write(bytes(publickey.exportKey('PEM'))); f.close()
На данный момент система шифрования на основе RSA считается надёжной, начиная с размера n в 2048 бит.
В системе RSA можно создавать сообщения, которые будут и зашифрованы, и содержать цифровую подпись. Для этого автор сначала должен добавить к сообщению свою цифровую подпись, а затем — зашифровать получившуюся в результате пару (состоящую из самого сообщения и подписи к нему) с помощью открытого ключа, принадлежащего получателю. Получатель расшифровывает полученное сообщение с помощью своего секретного ключа и проверяет подпись автора с помощью его открытого ключа.
Использование односторонней криптографической хеш-функции позволяет оптимизировать вышеописанный алгоритм цифровой подписи. Производится шифрование не самого сообщения, а значения хеш-функции, взятой от сообщения. Данный метод обеспечивает следующие преимущества:
1. Понижение вычислительной сложности. Как правило, документ значительно больше его хеша.
2. Повышение криптостойкости. Криптоаналитик не может, используя открытый ключ, подобрать подпись под сообщение, а только под его хеш.
3. Обеспечение совместимости. Большинство алгоритмов оперирует со строками бит данных, но некоторые используют другие представления. Хеш-функцию можно использовать для преобразования произвольного входного текста в подходящий формат.
Хэш-функции, представляют собой функции, математические или иные, которые получают на вход строку переменной длинны (называемую прообразом) и преобразуют ее в строку фиксированной, обычно меньшей, длинны (называемую значением хэш-функции). Смысл хэш-функции состоит в получении характерного признака прообраза — значения, по которому анализируются различные прообразы при решении обратной задачи. Однонаправленная хэш-функция — это хэш-функция, которая работает только в одном направлении: легко вычислить значение хэш-функции по прообразу, но трудно создать прообраз, значение хэш-функции которого равно заданной величине. Хэш-функция является открытой, тайны ее расчета не существует. Безопасность однонаправленной хэш-функции заключается именно в ее однонаправленности.
Однонаправленная функция H(M) применяется к сообщению произвольной длины М и возвращает значение фиксированной длинны h.
h = H(M), где h имеет длину m
Многие функции позволяют вычислить значение фиксированной длинны по входным данным произвольной длинны, но у однонаправленной хэш-функции есть дополнительные свойства, делающие их однонаправленными:
Зная М, легко вычислить h
Зная H, трудно определить М, для которого H(M) = h
Зная М, трудно определить другое сообщение, М', для которого H(M) = H(M')
Переходим к написанию первого пункта протокола:
1. Алиса подписывает сообщение своей цифровой подписью и шифрует ее открытым ключом Боба (асимметричным алгоритмом).
from Crypto.Hash import MD5
from Crypto.PublicKey import RSA
from Crypto import Random
from Crypto.Cipher import PKCS1_OAEP
# the creation of signature
f = open('c:\cipher\plaintext.txt','rb')
plaintext = f.read(); f.close()
randomnum = Random.new().read(16)
privatekey = RSA.importKey(open('c:\cipher\\alisaprivatekey.txt','rb').read())
myhash = MD5.new(plaintext).hexdigest()
signature = privatekey.sign(myhash, randomnum) # type tuple
# check long signature
signature = str(signature); a = len(signature); b = 16; c = 'aaaaaaaaaaaaaa'; i = 0
while a%b != 0:
i += 1
signature = signature + 'a'
a = len(signature)
if i > 0:
if i == 1:
signature = signature + c + '17'
if i > 1:
if i < 10:
num = '0'
signature = signature[0:-2] + num + str(i)
if i > 9:
signature = signature[0:-2] + str(i)
# signature encrypt
publickey = RSA.importKey(open('c:\cipher\\bobpublickey.txt','rb').read())
cipherrsa = PKCS1_OAEP.new(publickey)
a = len(signature); b = 16; c = a/b; i = 0; ii = -16; iii = 0
while i < c:
i += 1
ii += 16
iii += 16
if i == 1:
sig = cipherrsa.encrypt(signature[0:16])
if i > 1:
sig = sig + cipherrsa.encrypt(signature[ii:iii])
f = open('c:\cipher\signature.txt','wb')
f.write(bytes(sig)); f.close()
Количество байт в подписи должно быть кратно 16, иначе при шифровании асимметричным алгоритмом выдаст ошибку. Я добавил блок check long signature, который добавляет в подпись недостающее число байт и записывает это число в конец подписи. Перед проверкой подписи нужно удалить все эти символы. При шифровании каждый блок по 16 байт шифруется отдельно, для этого я использовал цикл. При генерации случайного числа (генератором псевдослучайных чисел) для шифра AES (переменная randomnum) в методе read обязательно указывайте длину кратную 128 бит или 16 байт.
Я использовал 128-битный алгоритм хеширования MD5.
В следующем листинге код для двух пунктов протокола:
2. Алиса генерирует случайный сеансовый ключ и шифрует этим ключом сообщение (с помощью симметричного алгоритма).
3. Сеансовый ключ шифруется открытым ключом Боба (асимметричным алгоритмом).
from Crypto.Cipher import AES
from Crypto import Random
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
# test long message file
f = open('c:\cipher\plaintext.txt','rb')
plaintext = f.read(); f.close()
a = len(plaintext); b = 16; i = 0
while a%b != 0:
i += 1
plaintext = plaintext + 'a'
a = len(plaintext)
if i > 0:
if i < 10:
num = '0'
plaintext = plaintext[0:-2] + num + str(i)
else:
plaintext = plaintext[0:-2] + str(i)
# the creation of a session key
sessionkey = Random.new().read(32) # 256 bit
# the encryption AES of the message
iv = Random.new().read(16) # 128 bit
obj = AES.new(sessionkey, AES.MODE_CBC, iv)
ciphertext = iv + obj.encrypt(plaintext)
f = open('c:\cipher\plaintext.txt','wb')
f.write(bytes(ciphertext)); f.close()
# the encryption RSA of the session key
publickey = RSA.importKey(open('c:\cipher\\bobpublickey.txt','rb').read())
cipherrsa = PKCS1_OAEP.new(publickey)
sessionkey = cipherrsa.encrypt(sessionkey)
f = open('c:\cipher\sessionkey.txt','wb')
f.write(bytes(sessionkey)); f.close()
Количество байт в сообщении должно быть кратно 16. Как и в случае с подписью я изменил исходное сообщение, затем создал сессионный ключ размером 256 бит. Ну и конечно зашифровал сессионный ключ с помощью открытого ключа Боба.
для режима CBC требуется вектор инициализации (IV) (переменная iv).
В криптографии, вектор инициализации (IV) представляет собой некоторое число, как правило оно должно быть случайным или псевдослучайным. Случайность имеет решающее значение для достижения семантической безопасности, которая при повторном использовании схемы под тем же ключом не позволит злоумышленнику вывести отношения между сегментами зашифрованных сообщений. Вектор инициализации не шифруется и сохраняется перед зашифрованным сообщением.
Далее Алиса посылает Бобу зашифрованное сообщение, подпись и зашифрованный сеансовый ключ.
Боб получает зашифрованное сообщение Алисы, подпись и зашифрованный сеансовый ключ.
4. Боб расшифровывает сеансовый ключ своим закрытым ключом.
5. При помощи полученного, таким образом, сеансового ключа Боб расшифровывает зашифрованное сообщение Алисы.
from Crypto.Cipher import AES
from Crypto import Random
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
# the decryption session key
privatekey = RSA.importKey(open('c:\cipher\\bobprivatekey.txt','rb').read())
cipherrsa = PKCS1_OAEP.new(privatekey)
f = open('c:\cipher\sessionkey.txt','rb')
sessionkey = f.read(); f.close()
sessionkey = cipherrsa.decrypt(sessionkey)
# the decryption and reception of the IV vector
f = open('c:\cipher\plaintext.txt','rb')
ciphertext = f.read(); f.close()
iv = ciphertext[:16]
obj = AES.new(sessionkey, AES.MODE_CBC, iv)
plaintext = obj.decrypt(ciphertext)
f = open('c:\cipher\plaintext.txt','wb')
f.write(bytes(plaintext[16:])); f.close()
# remove unnecessary
f = open('c:\cipher\plaintext.txt','rb')
plaintext = f.read(); f.close()
num = plaintext[-2:]
f = open('c:\cipher\plaintext.txt','wb')
f.write(bytes(plaintext[:-int(num)])); f.close()
Для дешифрования не забывайте получить вектор инициализации, который находится в первых 16 байтах шифротекста.
В блоке remove unnecessary мы удаляем уже ненужные символы, которые мы добавляли в сообщение для его шифрования (дина сообщения должна быть кратна 16).
Последний и самый трудный этап:
6. Боб расшифровывает и проверяет подпись Алисы.
from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA
from Crypto.Hash import MD5
# decrypt the signature
f = open('c:\cipher\signature.txt','rb')
signature = f.read(); f.close()
privatekey = RSA.importKey(open('c:\cipher\\bobprivatekey.txt','rb').read())
cipherrsa = PKCS1_OAEP.new(privatekey)
a = len(signature); b = 256; c = a/b; i = 0; ii = -256; iii = 0
while i < c:
i += 1
ii += 256
iii += 256
if i == 1:
sig = cipherrsa.decrypt(signature[0:256])
if i > 1:
sig = sig + cipherrsa.decrypt(signature[ii:iii])
signature = sig
num = signature[-2:]
signature = signature[:-int(num)]
# signature verification
f = open('c:\cipher\plaintext.txt','rb')
plaintext = f.read(); f.close()
publickey = RSA.importKey(open('c:\cipher\\alisapublickey.txt','rb').read())
myhash = MD5.new(plaintext).hexdigest()
t = signature
t = t[1:-3]
t = int(t)
t = (t,)
test = publickey.verify(myhash, t)
test = signature + str(test)
f = open('c:\cipher\signature.txt','wb')
f.write(bytes(test)); f.close()
Каждые 16 байт подписи зашифровывались в 256 байт шифротекста, поэтому подпись дешифруется блоками по 256 байт. Подпись это кортеж, поэтому строку signature нужно обязательно преобразовать в кортеж. После проверки подписи, в конец файла signature.txt добавится True — в случае успешной проверки или False если сообщение после подписания было изменено.
Безопасность RSA основана на сложности задачи факторизации произведения двух больших простых чисел. Факторизация целых чисел для больших чисел является задачей большой сложности. Не существует никакого известного способа, чтобы решить эту задачу быстро. Факторизация кандидат в односторонние функции, которые относительно легко вычисляются, но инвертируются с большим трудом. То есть, зная x просто рассчитать f(x), но по известному f(x) нелегко вычислить x. Здесь, «нелегко» означает, что для вычисления x по f(x) могут потребоваться миллионы лет, даже если над этой проблемой будут биться все компьютеры мира.
Литература:
Брюс Шнайер — Прикладная криптография