201309290938


  За двумя зайцами погонишься, ни одного не поймаешь. Зайцев должно быть не менее трех.

5. Шифрование
   ----------

Почему иногда шифруют информацию (точка зрения)?

Ограничение доступа к информации приводит к одновременному существованию множества (N > 1) несвязанных или слабо связанных объектов -- основы эволюционного способа развития.


Как работает механизм шифрования
--------------------------------

Достаточно рассмотреть следующие темы

  - представление различных форм информации (текст, картинка, аудио- и/или видео- дорожки) в виде целого числа конечной длины.
  - сокрытие и извлечение числа с помощью другого числа (ключа) - cryption / encryption. Симметричные методы шифрования.
  - ассимметричные методы шифрования (на примере RSA).
  - кубиты и квантовые алгоритмы.
  
Изучение каждой отдельной темы, впрочем, в зависимости от уровня детализации, может занять много времени и сил.


Как применять технологию шифрования
-----------------------------------

Шифрование/дешифрование рассмотрим на примере OpenSSL - см. Приложения Б., В. (Другой популярный пакет PGP 7.03 [17], можно изучить самостоятельно).


Немного теории
--------------

Часто применяемым способом сокрытия информации является ее кодирование (шифрование) с последующим декодированием (расшифровка). Используется терминология:

  - plain text (сообщение открытым текстом) [7]
  - ciphertext (шифровка) [8]
  - encrypted line (закрытый канал связи) [9]
  - key (криптографический ключ) [10]
  . . .
  
Зашифрованное сообщения предназначается доверенным лицам, имеющим ключ для расшифровки сообщения. Перехват сообщения устанавливает факт его передачи, не раскрывая его содержания. Для заполучения содержания перехваченного сообщения могут быть использованы:

  - backdoor (намеренно оставленный метод доступа в обход ключа)
  - уязвимости системы шифрования
  - master key или 2-nd key (если алгоритм допускает дешифрование более чем одним ключем)
  - взлом шифра (криптология)
  
Пример

  передающая сторона: я (позавчера) написал и зашифровал
  получающая сторона: я (вчера) - расшифровал и прочел
  взломщик: я (сегодня) - утратил ключ и забыл текст сообщения
  
По мере развития общества методы шифрования и взлома совершенствовались. Остановимся на некоторых из них

  Шифр Юлия Цезаря (Caesar cipher) [11] ~70 b.c
  Решетка Кардано (Cardan grille) [12] 1550
  DES [13] ~ 1971
  3DES [14] 1998
  AES [15] 2001
  Квантовые методы (настоящее время)
  
На сегодняшнее время слабые шифры (легко взламываемые) хорошо подходят для целей обучения. Чем сильнее алгоритм шифрования, тем более мощного железа он требует при взломе:

  - Персональные компьютеры (1-1024 ядер, часто используются шейдеры графической карты)
  - Фоновые мощности интернета (проект Seti, Rainbow-tables и др.)
  - Суперкомпьютерные гриды
  - Квантовые компьютеры

Соответственно, растут временные и денежные затраты по взлому. Для снижения временных затрат на поиск ключа перебором (brute force), ключи, найденные в режиме 24/7, накапливаются в распределенные базы данных для поражения реальных целей.


Симметричное шифрование
-----------------------

Если обе стороны имеют ключи шифрования и дешифрования (либо это один ключ) - говорят о симметричном шифровании. В этом случае оба ключа секретны.


Асимметричное шифрование. Цифровая подпись
------------------------------------------

Асимметричный метод (шифрующий и декодирующий ключи различны) подходит для двух применений. В таком методе один ключ (private) - секретный а другой (public) может быть обнародован.

  1. сообщение шифруется private-ключем а расшифровывается с помощью public-ключа. Подходит для цифровой подписи документа, когда по публичному ключу становися известен обладатель секретного ключа. Такой документ легко прочесть, но трудно подделать.

  2. сообщение шифруется public-ключем а расшифровывается с помощью private-ключа. Аналогия: Боб отдает Алисе единственный ключ от входной двери и, уходя, запирает ее захлопыванием (шнепперный замо'к) -- открыть ее может только обладатель ключа Алисы (часто сама Алиса).


Использование обманных ключей
-----------------------------

В этом случае казалось-бы успешный взлом сообщения извлекает из шифровки ложный текст.


Перекодировки
-------------

Похожая на дешифрование операция перекодировки актуальна, если одновременно используется несколько различных кодировок текста. Так, в случае кириллицы, популярными кодировками являются CP866, Cp1251, KOI8R, UTF-8, UTF-16, UTF16 big endian и некоторые другие. Так, например, выглядит фрагмент этой главы, отображенный в консоли Windows на кодовой странице 437 (текст файла набран в UTF-8 с BOM):

∩╗┐201309290938

    ╨ù╨░ ╨┤╨▓╤â╨╝╤Å ╨╖╨░╨╣╤å╨░╨╝╨╕ ╨┐╨╛╨│╨╛╨╜╨╕╤ê╤î╤ü╤Å, ╨╜╨╕ ╨╛╨┤╨╜╨╛╨│╨╛ ╨╜╨╡╨┐╨╛╨╣╨╝╨░╨╡╤ê╤î. ╨ù╨░╨╣╤å╨╡╨▓ ╨┤╨╛╨╗╨╢╨╜╨╛ ╨▒╤ï╤é╤î ╨╜╨╡ ╨╝╨╡╨╜╨╡╨╡ ╤é╤Ç╨╡╤à.

5. ╨¿╨╕╤ä╤Ç╨╛╨▓╨░╨╜╨╕╨╡

╨º╨░╤ü╤é╨╛ ╨┐╤Ç╨╕╨╝╨╡╨╜╤Å╨╡╨╝╤ï╨╝ ╤ü╨┐╨╛╤ü╨╛╨▒╨╛╨╝ ╤ü╨╛╨║╤Ç╤ï╤é╨╕╤Å ╨╕╨╜╤ä╨╛╤Ç╨╝╨░╤å╨╕╨╕ ╤Å╨▓╨╗╤Å╨╡╤é╤ü╤Å ╨╡╨╡╨║╨╛╨┤╨╕╤Ç╨╛╨▓╨░╨╜╨╕╨╡ (╤ê╨╕╤ä╤Ç╨╛╨▓╨░╨╜╨╕╨╡) ╤ü╨┐╨╛╤ü╨╗╨╡╨┤╤â╤Ä╤ë╨╕╨╝ ╨┤╨╡╨║╨╛╨┤╨╕╤Ç╨╛╨▓╨░╨╜╨╕╨╡╨╝(╤Ç╨░╤ü╤ê╨╕╤ä╤Ç╨╛╨▓╨║╨░). ╨ÿ╤ü╨┐╨╛╨╗╤î╨╖╤â╨╡╤é╤ü╤Å ╤é╨╡╤Ç╨╝╨╕╨╜╨╛╨╗╨╛╨│╨╕╤Å:

Все популярные современные языки имеют библиотеки функций/классов по перекодировке текстовых строк. Например C# -- код перекодировки между UTF-8 b CP1251. (https://forum.antichat.ru)

проверить работоспособность кода:

  private string Win1251ToUTF8(string source)
  {
    Encoding utf8 = Encoding.GetEncoding("utf-8");
    Encoding win1251 = Encoding.GetEncoding("windows-1251");

    byte[] utf8Bytes = win1251.GetBytes(source);
    byte[] win1251Bytes = Encoding.Convert(win1251, utf8, utf8Bytes);
    source = win1251.GetString(win1251Bytes);
    return source;
  }

  private string UTF8ToWin1251(string source)
  {
    Encoding win1251 = Encoding.GetEncoding("windows-1251");
    Encoding utf8 = Encoding.GetEncoding("utf-8");

    byte[] win1251Bytes = win1251.GetBytes(source);
    byte[] utf8Bytes = Encoding.Convert(win1251, utf8, utf8Bytes);
    source = utf8.GetString(utf8Bytes);
    return source;
  }


Ссылки:

 [7]. Plaintext. http://en.wikipedia.org/wiki/Plaintext
 [8]. Ciphertext. http://en.wikipedia.org/wiki/Ciphertext
 [9]. Link encryption. http://en.wikipedia.org/wiki/Link_encryption
[10]. Key. http://en.wikipedia.org/wiki/Key_(cryptography)
[11]. http://en.wikipedia.org/wiki/Caesar_cipher
[12]. http://en.wikipedia.org/wiki/Cardan_grille
[13]. http://en.wikipedia.org/wiki/Data_Encryption_Standard
[14]. http://en.wikipedia.org/wiki/Triple_DES
[15]. http://en.wikipedia.org/wiki/Advanced_Encryption_Standard
[16]. http://www.slproweb.com/products/Win32OpenSSL.html
[17]. http://www.pitt.edu/~poole/accessiblePGP703.htm

------------------------------------------------------------------------

Приложение А. RSA

Алгоритм RSA был назван в честь  его авторов Ron Rivest, Adi Shamir и Len Adleman (1977)

Определение:

  a = c * n + r
  r = a mod n 

1. открытый ключ (public key)  e,N:

  N - модуль (modulus), 
  e - секретный ключ (encryption key, exponent)

  N = p * q,  где p и q неодинаковые простые числа. (where p and q are distinct primes).
  f = (p-1)(q-1)
  
  1 < e < N such that gcd(e, f)=1* На практике e обычно 3, 17 или 65537. Это простые числа Ferma, иногда обозначаемые как F0, F2 и F4 соответственно: Fx = 2 ^ ( 2 ^ x ) + 1
                                  
*) gcd - greatest common divider - наибольший общий делитель

2. секретный ключ (private key) N,d:   

  N - модуль (modulus), 
  d - ключ расшифровки (decryption key).

                                Python             Raptor

  e * d mod f = 1               pow(e*d, 1, f)     powermod(..

  Cipher = Plain ** e mod N     pow(Plain, e, N)   powermod(..
  Plain = Cipher ** d mod N.    pow(Cipher, d, N)  powermod(..

Пример.

  p = 61   q = 53 
  N = 61 * 53 = 3233 
  f = 60 * 52 = 3120
  e = 17
  d = 2753   2753 * 17 = 1 + 15 * 3120

  Plain = 123

  Cipher = 123 ^ 17 mod 3233   = 855
  Plain  = 855 ^ 2753 mod 3233 = 123

Замечание: Для этого примера максимальная длина Plain вероятно N - 2 

Ссылки:

    http://en.wikipedia.org/wiki/RSA
    http://www.di-mgt.com.au/rsa_alg.html
    http://python.org/ftp/python/2.6/python-2.6.msi

  Список первых 10000 простых чисел (the list of smallest primes)

    http://www.math.utah.edu/~pa/math/p10000.html

------------------------------------------------------------------------

Приложение Б. RSA и OpenSSL для начинающих:

Попросить подсказку

  man openssl
  man rsa
  man rsautl

Кодировать файл foo.bin в base64, результат сохранить в foo.bin.b64:

  openssl base64 -in foo.bin -out foo.bin.b64
  cat foo.bin.b64
  8dLS+STphqyG/fezbJS83zK+7BU=

Раскодировать полученный файл обратно (foo.bin.b64 в foo.bin)

  openssl base64 -in foo.bin.b64 -out foo.bin -d

Сгенерировать RSA 512 битный секретный ключ (минимально 32 бита, 4096 бит займет некоторое время)

  openssl genrsa -out priv.rsa 512

На основе секретного ключа сгенерировать открытый ключ (Generating public key based on just generated private key)

  openssl rsa -in priv.rsa -pubout -out pub.rsa

Зашифровать файл cc.txt открытым ключем (Encrypting session key with RSA public key).

  openssl rsautl -encrypt -inkey pub.rsa -in cc.txt -out cc.enc -pubin

Расшифровать файл cc.enc секретным ключем

  openssl rsautl -decrypt -inkey priv.rsa -in cc.enc

Подписать хэш секретным ключем (Signing message digest with RSA private key).

  openssl rsautl -sign -inkey priv.rsa -in cc.txt -out cc.sig

Верифицировать подпись открытым ключем (Verifying signature with RSA public key).

  openssl rsautl -verify -inkey pub.rsa -in cc.sig -pubin

Прочесть открытый ключ (Examining RSA public key).

  cat pub.rsa

-----BEGIN PUBLIC KEY-----
MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAKWbcsiNshrfT2jTavqtmvV+AX89JbBI
YGYBNFLvN1PBHDfCj09wu0PENKicwD09EXDhuOUJZ0NyYEOSFjpWvGkCAwEAAQ==
-----END PUBLIC KEY-----

  openssl rsa -in pub.rsa -pubin -text

Modulus (512 bit):
    00:a5:9b:72:c8:8d:b2:1a:df:4f:68:d3:6a:fa:ad:
    9a:f5:7e:01:7f:3d:25:b0:48:60:66:01:34:52:ef:
    37:53:c1:1c:37:c2:8f:4f:70:bb:43:c4:34:a8:9c:
    c0:3d:3d:11:70:e1:b8:e5:09:67:43:72:60:43:92:
    16:3a:56:bc:69
Exponent: 65537 (0x10001)
-----BEGIN PUBLIC KEY-----
MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAKWbcsiNshrfT2jTavqtmvV+AX89JbBI
YGYBNFLvN1PBHDfCj09wu0PENKicwD09EXDhuOUJZ0NyYEOSFjpWvGkCAwEAAQ==
-----END PUBLIC KEY-----

Прочесть секретный ключ (Examining RSA private key)

  openssl rsa -in priv.rsa -text

Private-Key: (512 bit)
modulus:
    00:a5:9b:72:c8:8d:b2:1a:df:4f:68:d3:6a:fa:ad:
    9a:f5:7e:01:7f:3d:25:b0:48:60:66:01:34:52:ef:
    37:53:c1:1c:37:c2:8f:4f:70:bb:43:c4:34:a8:9c:
    c0:3d:3d:11:70:e1:b8:e5:09:67:43:72:60:43:92:
    16:3a:56:bc:69
publicExponent: 65537 (0x10001)
privateExponent:
    21:b6:34:36:89:49:b1:58:b6:14:93:bd:1a:4c:8e:
    d7:dc:8f:b7:74:1e:20:f5:8a:d2:18:fa:aa:cb:51:
    8a:f5:d7:c7:35:f9:40:a3:97:06:45:f9:2d:fd:1d:
    dd:63:c1:12:b0:5a:b5:bc:09:a3:00:70:52:71:df:
    f1:ab:ed:51
prime1:
    00:d4:4d:85:3f:be:63:6c:5b:89:86:b2:56:af:4b:
    41:f2:5e:f9:84:29:af:ed:cc:7c:dc:d7:2d:26:82:
    2c:4d:0d
prime2:
    00:c7:b1:7b:b9:3f:67:ec:cb:ec:ef:b4:42:0a:10:
    dd:01:47:b9:51:d6:fc:89:01:ca:2d:b0:79:13:cd:
    a8:ed:cd
exponent1:
    00:80:53:b3:5d:8a:79:92:7f:ea:2b:2f:15:52:b4:
    0c:d2:b2:31:e4:7f:46:46:59:3a:88:4a:d0:91:dc:
    51:66:e9
exponent2:
    00:ae:a4:c6:33:c9:04:36:d0:52:33:81:4e:90:47:
    17:41:db:5c:73:fa:b5:79:8d:1b:28:c2:41:e1:d3:
    e7:7d:b1
coefficient:
    2c:0a:28:6c:34:d4:09:8f:f1:6e:31:77:bc:5d:d3:
    1a:49:dc:5b:8f:42:ba:5b:14:43:82:08:52:52:b0:
    55:9f
-----BEGIN RSA PRIVATE KEY-----
MIIBOwIBAAJBAKWbcsiNshrfT2jTavqtmvV+AX89JbBIYGYBNFLvN1PBHDfCj09w
u0PENKicwD09EXDhuOUJZ0NyYEOSFjpWvGkCAwEAAQJAIbY0NolJsVi2FJO9GkyO
19yPt3QeIPWK0hj6qstRivXXxzX5QKOXBkX5Lf0d3WPBErBatbwJowBwUnHf8avt
UQIhANRNhT++Y2xbiYayVq9LQfJe+YQpr+3MfNzXLSaCLE0NAiEAx7F7uT9n7Mvs
77RCChDdAUe5Udb8iQHKLbB5E82o7c0CIQCAU7NdinmSf+orLxVStAzSsjHkf0ZG
WTqIStCR3FFm6QIhAK6kxjPJBDbQUjOBTpBHF0HbXHP6tXmNGyjCQeHT532xAiAs
CihsNNQJj/FuMXe8XdMaSdxbj0K6WxRDgghSUrBVnw==
-----END RSA PRIVATE KEY-----

Ссылки:

  Openssl for Windows

[18]. http://www.slproweb.com/products/Win32OpenSSL.html
[19]. http://www.madboa.com/geek/openssl/

------------------------------------------------------------------------

Приложение В. openssl и AES

  http://stackoverflow.com/questions/8343894/aes-encrypt-with-openssl-command-line-tool-and-decrypt-in-java
  http://www.madboa.com/geek/openssl/
  
Зашифровка и расшифровка в командной строке с помощью openssl/AES:

  #!/bin/bash

  key128="01020304050607080900010203040506"
  iv="01020304050607080900010203040506"
  openssl enc -aes-128-cbc -in mytext -out mytext.enc -K $key128 -iv $iv
  openssl enc -d -aes-128-cbc -in mytext.enc -K $key128 -iv $iv
