Как стать автором
Обновить
  • по релевантности
  • по времени
  • по рейтингу

Факторизация чисел и методы решета. Часть I

Информационная безопасность *Криптография *Алгоритмы *Математика *Научно-популярное



В работе рассматривается традиционный подход, который автором в ряде статей критикуется.
Здесь я воздержусь от критики, и направлю свои усилия на разъяснение сложных моментов в традиционном подходе. Весь арсенал существующих методов не решает задачу факторизации в принципе, так как почти все решеточные и другие алгоритмы построены на жесткой связи и зависимости времени их выполнения от разрядности факторизуемого числа N. Но замечу, что у чисел имеются и другие свойства кроме разрядности, которые можно использовать в алгоритмах факторизации.

Оценки сложности — эвристические опираются на рассуждения ограниченные авторским пониманием проблемы. Пора бы уже понять, что факторизация чисел в глубоком тупике, а математикам (не только им) пересмотреть свое отношение к проблеме и создать новые модели.

Простая идея факторизации целого нечетного числа N исторически — состоит в поиске пары квадратов чисел разной четности, разность которых кратна kN, при k =1 разложение успешно реализуется так как в этом случае сразу получаем произведение двух скобок $N = x^2 -y^2 =(x - y)(x + y)$ c сомножителями N. При k>1 случаются тривиальные разложения.

Таким образом, проблема факторизации преобразуется в проблему поиска подходящих квадратов чисел. Понимали эти факты многие математики, но П. Ферма первым в 1643 году реализовал идею поиска таких квадратов в алгоритме, названном его именем. Перепишем иначе приведенное соотношение $ x^2-N =y^2 $.

Если разность слева от равенства не равна квадрату, то изменяя х, можно подобрать другой квадрат, чтобы и справа получался квадрат. Практически все нынешние алгоритмы используют эту идею (поиска пары квадратов), но судя по результатам, похоже, что идея себя исчерпала.
Читать дальше →
Всего голосов 21: ↑20 и ↓1 +19
Просмотры 8.1K
Комментарии 3

Программисты разгадали очередной шифр убийцы Зодиака спустя полвека

Криптография *История IT
imageФото: zodiackillerfacts.com

Международная команда взломщиков, в которую входили специалисты из США, Австралии и Бельгии, смогла разгадать шифр серийного убийцы по прозвищу Зодиак, который так и не был пойман. Этому шифру 51 год. Зодиак отправил его в американскую газету San Francisco Chronicle в 1969 году.
Всего голосов 39: ↑37 и ↓2 +35
Просмотры 18K
Комментарии 10

Стартап Red Balloon Security высылает соискателям в качестве теста жёсткий диск с криптовалютным кошельком

Информационная безопасность *Карьера в IT-индустрии IT-компании

Тестовый набор для соискателя в Red Balloon Security — конфеты (много драже Nerds, Fun-Dip и Poprocks), адаптер для HDD, зашифрованный жёсткий диск (Seagate ST3250312AS, 250 ГБ) и небольшую инструкцию

По информации Business Insider, стартап кибербезопасности Red Balloon Security необычным образом проводит тест для соискателей на работу в компании. Кандидату предлагается расшифровать данные на жёстком диске, там находится криптовалютный кошелек с 0,1337 биткоина и GPS-координаты для встречи с представителем стартапа.

Комплекты для тестирования стартап высылает почти всем желающим, кто подал заявку. Немногие, кто получил подобную посылку, смогли решить задачу. Red Balloon Security регулярно меняет элементы теста, чтобы соискатели не делились своими наработками в Интернете.
Читать дальше →
Всего голосов 12: ↑12 и ↓0 +12
Просмотры 8.4K
Комментарии 11

Шифр Аль-Кайды взломали

Информационная безопасность *
Британская спецслужба МИ5 инициировала утечку в прессе информации об успешном взломе секретного шифра террористической организации Аль-Кайда. Для работы над этой задачей в штаб-квартире в Менвит-Хилл (Menwith Hill) на севере Англии была организована специальная команда взломщиков из специалистов МИ5 и АНБ. Расшифровка заняла шесть месяцев.

С помощью этого кода арестованные в Великобритании лидеры Аль-Кайды обменивались сообщениями друг с другом, а также управляли сетью агентов.

Шифр был основан на замене букв по таблице, известной авторам. Как сообщатся, в качестве таблицы террористы использовали известные им наизусть религиозные трактаты, а в посланиях использовали слова на как минимум на двадцати различных диалектах Афганистана, Ирана, Пакистана, Йемена и Судана.
Читать дальше →
Всего голосов 72: ↑54 и ↓18 +36
Просмотры 1.9K
Комментарии 79

No robot: зашифровка текста на веб-странице

Информационная безопасность *
В Сети появился оригинальный сервис Norbt (No robot), который позволяет любому желающему создать за пару секунд свою собственную страничку с зашифрованным текстом. Увидеть содержимое страницы можно только зная пароль.

Создатели веб-приложения утверждают, что здесь используется стойкая криптография, так что даже в случае взлома сервера хакер не сможет расшифровать текст. Данные на сервере хранятся в таком виде:

Answer: SHA1(answer + salt1), salt1
Text: AES128(SHA1(answer + salt2), IV, Mode.CFB, text), salt2, IV


То есть чтобы расшифровать текст, хакеру придётся взломать или SHA1(answer + salt1), или AES128.

Прослушивание трафика путём взлома SSL тоже не поможет хакеру, потому что все операции шифрования выполняются в браузере.
Всего голосов 48: ↑37 и ↓11 +26
Просмотры 774
Комментарии 30

ГОСТ 28147-89 (Часть 1. Введение и общие принципы)

Информационная безопасность *
Очень часто на Хабре встречаются статьи о сути, программных реализациях, вскрытиях шифров. Но непонятно одно: почему среди них нет наших, отечественных алгоритмов шифрования?

Я решил исправить это, написав повесть статью, разбитую на 5 частей для лучшего восприятия о стандарте ГОСТ 28147-89. Каждая часть, кроме первой (описывает схему алгоритма и общие принципы), повествует о каждом из четырех возможных режимах работы стандарта с приложением к ним кода на C++.
Введение в ГОСТ 28147-89
Всего голосов 52: ↑43 и ↓9 +34
Просмотры 51K
Комментарии 96

ГОСТ 28147-89 (Часть 2. Режим простой замены)

Информационная безопасность *
Эта статья является продолжением статьи про ГОСТ 28147-89. Как уже говорилось ранее, ГОСТ 28147-89 поддерживает четыре режима работы, но, пожалуй, главным из них является режим простой замены, который используется как самостоятельно, так и как составная часть других режимов.
В статье приведен код на c++, реализующий данный режим.
Что же это за режим такой?
Всего голосов 13: ↑7 и ↓6 +1
Просмотры 48K
Комментарии 19

Модификация шифра Виженера

Чулан
Недавно в личных целях понадобилось использовать некий простой шифр для сокрытия информации. Изначально хотел использовать старый добрый шифр Цезаря, где каждый символ заменяется другим, сдвинутым на фиксированное число позиций (например, при сдвиге на одну позицию получаем АРКА -> БСЛБ). Однако, в случае шифрования небольших объемов информации и в случаях наличия в исходном тексте повторяющихся букв шифр взламывается за считанные секунды (например, в нашем случае сдвига на единицу «ООО БАРК» -> «ППП ВБСЛ»). В результате выбор пал на шифр Виженера, достаточно простой в реализации и более стойкий ко взлому…

Читать дальше →
Всего голосов 14: ↑9 и ↓5 +4
Просмотры 2.5K
Комментарии 21

ФБР просит помощи в расшифровке сообщения 1999 года

Криптография *
ФБР обратилось за помощью к сообществу гражданских криптоаналитиков за помощью в расшифровке предсмертного послания, которое было найдено 30 июня 1999 года в карманах жертвы преступления Рикки Маккормика (Ricky McCormick) из Сент-Луиса.

Скан записок на сайте ФБР

ФБР сообщает, что «несмотря на тщательную работу отдела криптоанализа (CRRU) и Американской ассоциации криптограмм, значение этих двух зашифрованных записок остаётся загадкой».
Читать дальше →
Всего голосов 110: ↑106 и ↓4 +102
Просмотры 13K
Комментарии 243

Крипто-шифр «пасьянс»

Криптография *
Алгоритм поточного шифрования SOLlTAlRE (ПАСЬЯНС) предложен Б. Шнайером в 1999 г. Шифр до безумия красив и я не понимаю, почему на Хабре его еще никто не осветил. Неужели никто не читал «Криптономикон» Стивенсона? Собственно после прочтения книги не могу пройти мимо сего чуда.

Из теории, это поточный шифр с обратной связью по выходу. Из поточности следует, что каждому символу изначальной последовательности будет соответствовать символ зашифрованной. Для тех, кто не знает, к примеру, существуют еще блочные шифры, в них шифрование происходит блоками (несколькими байтами или символами). Далее существует очень много видов сцепления блоков текста и так называемой гаммы (некой случайной секретной последовательности). В данном случае используется обратная связь по выходу, т.е. каждый символ гаммы изменяет состояние гаммы.

Читать дальше →
Всего голосов 32: ↑27 и ↓5 +22
Просмотры 14K
Комментарии 38

В скриншотах игры WoW обнаружены цифровые водяные знаки (userID, time, realm)

Криптография *Обработка изображений *


Пользователи игрового форума OwnedCore обнаружили скрытые водяные знаки, которые автоматически внедряются в JPG-файлы, если вы делаете скриншот в игре World of Warcraft. Если сделать скриншот чистой области, открыть файл в IrfanView или каком-нибудь редакторе, увеличить резкость с максимальной настройкой фильтра, повторить процедуру несколько раз, то заметен явный паттерн, который многократно повторяется.

Пользователи уже написали программку, которая автоматически извлекает информацию из водяных знаков. Это незашифрованный текст ASCII, содержащий имя пользователя, время снятия скриншота с точностью до минуты и IP-адрес реалма, включая приватные сервера.
Читать дальше →
Всего голосов 103: ↑97 и ↓6 +91
Просмотры 101K
Комментарии 67

Найдены останки голубя с криптограммой Второй мировой войны

Криптография *

Спустя почти 70 лет после окончания Второй мировой войны в дымоходе одного из особняков деревни Блетчингли, Великобритания были обнаружены останки голубя с привязанным к лапе почтовым контейнером красного цвета.
Читать дальше →
Всего голосов 103: ↑92 и ↓11 +81
Просмотры 90K
Комментарии 86

Криптографы Великобритании так и не расшифровали код, переданный с голубем

Криптография *


Британские криптографы в сотрудничестве с Центром Правительственной Связи потратили несколько недель на расшифровку кода, который был найден вместе со скелетом голубя. Теперь специалисты уверены, что этот код так и не получится расшифровать без доступа к исходным криптографическим данным.
Читать дальше →
Всего голосов 22: ↑21 и ↓1 +20
Просмотры 25K
Комментарии 53

Cicada 3301: Охота продолжается в 2014

Криптография *
Перевод
Первая часть.

Несмотря на опасения, что огласка в СМИ помешает этому, Cicada начала новый набор в свои ряды 6 января 2014 года.

Большая популярность этого квеста означала появление огромного количества поддельных картинок от людей, выдающих себя за «Цикад», что собственно и произошло. С первых чисел января, 4chan начал заполнятся «черными картинками с белым текстом» выдающими себя за новые задания. Однако 5 января, через день после обычного срока публикации первого задания, когда все уже начали расходиться, а последняя надежда была потеряна…
Что произошло дальше?
Всего голосов 102: ↑93 и ↓9 +84
Просмотры 47K
Комментарии 16

Почему Spritz стал столь популярным за последние несколько недель

Информационная безопасность *Криптография *


Привет, уважаемые криптографы и математики!


Мне, не профессиональному математику и не криптографу, бывает сразу сложно понять, как устроен алгоритм шифрования. Перед вами попытка разобраться с отдельными функциями одного алгоритма. А так же, понять, почему Spritz алгоритм сейчас более обсуждаем специалистами, чем, например, Keccak. На Хабре было несколько статей, которые описывали Sponge функцию, или, по-русски, губку (один, два). Эта функция может использоваться несколькими способами: как криптор\декриптор, как хеш, как хеш с раздельными доменами, формировать код аутентичности сообщения (MAC) или имитовставку, работать как потоковый шифр и как потоковый шифр с произвольным доступом, для аутентификации с ассоциированными данными (Authenticated Encryption with Associated Data), как генератор псевдослучайных чисел и для генерации симметричных ключей из паролей.
Читать дальше →
Всего голосов 47: ↑30 и ↓17 +13
Просмотры 21K
Комментарии 11

Хагелин — гений научно-технической мысли

Блог компании ua-hosting.company Информационная безопасность *Криптография *Разработка систем связи *
Легендарный изобретатель шифровальных машин — Борис Цезарь Вильгельм Хагелин (1892 -1983).

Не существует приложений связи, где бы не были применены решения, разработанные фирмой Crypto AG, которую более чем 60 лет назад основал талантливый криптограф Борис Хагелин.



Номенклатура аппаратуры и программного обеспечения Crypto AG исключительно широка. Известна компания не только шифртехникой для правительственной и военной связи. В офисах большая часть ежедневного обмена сообщениями и данными всё ещё идёт по классическим каналам – PSTN/ISDN, аналоговой или цифровой телефонии и факсу. Конфиденциальность переговоров, факсов и информации в ноутбуках обеспечивается рядом аппаратных решений Crypto AG: PSTN Encryption HC-2203, Secure GSM HC-2423, Fax Ecryption HC-4221, Crypto PC Security HC-6360, Crypto Laptop HC-6835 и другими. Для военных и гражданских применений разработаны
Читать дальше
Всего голосов 20: ↑20 и ↓0 +20
Просмотры 14K
Комментарии 0

Шифрование машины Purple

Блог компании ua-hosting.company Информационная безопасность *Криптография *
В годы второй мировой войны японские специалисты трудились над разработкой шифровальных систем, названия которым давались по цветовым оттенкам. В середине 30-х американская разведка выявила тайный шифр — «пурпурный» код. В результате работ специальной команды, которую возглавил знаменитый американский криптограф Уильям Фредерик Фридман, было установлено, что японцы используют новую шифровальную машину. Фридман усердно занялся расшифровкой «пурпурного» кода — одного из самых сложных. И в 1940 г. работа дала результаты, код был взломан, а его алгоритм — опубликован. Взлом японского шифра помог разведке США получить доступ к секретной дипломатической корреспонденции.

Что же до шифровального устройства, то американцы изначально предполагали, что имеют дело с одной из версий «Энигмы». Но вскоре обнаружилось, что «пурпурный» код принадлежит японской шифровальной машине с кодовым названием Purple. В Японии она известна под названиями «Алфавитная печатная машина типа 97» (в оригинале 九七式欧文印字機) или «Шифровальная машина типа B» (в оригинале 暗号機 タイプ). Purple заменила шифраторы Red, которые использовались Министерством иностранных дел Японии.



Читать дальше →
Всего голосов 16: ↑13 и ↓3 +10
Просмотры 12K
Комментарии 0

Асимметричная криптография и криптография с открытым ключом — это не одно и то же?

Информационная безопасность *Криптография *
В данной заметке я хотел бы поделиться своими соображениями, касающимися криптографической терминологии. Конечно, ответ на вопрос, который вынесен в заголовок (будь он положительным или нет) никак не повлияет на работоспособность и безопасность соответствующих криптоалгоритмов, но здесь своей целью я ставлю исключительно разобраться в их классификации.

Во многих учебниках, справочниках и ресурсах сети Интернет утверждается, что «асимметричная криптография» и «криптография с открытым ключом» являются синонимами, равно как «симметричная криптография» и «криптография с секретным ключом». Но в случае симметричной криптографии вопросов, во всяком случае у меня, не возникает. Там есть и секретный ключ, и симметричность, выражающаяся в том, что обе взаимодействующие стороны имеют одинаковый ключ.

В случае же асимметричной криптографии дело обстоит по-другому. Возьмем, например, такие алгоритмы, как «шифр Шамира» [ШШ] или «ментальный покер» [МП]. Они, несомненно, являются асимметричными, но назвать их шифрами с открытым ключом язык не поворачивается, поскольку открытых ключей в них вообще нет (за исключением общих для всех абонентов параметров, таких как модуль и генератор группы).
Читать дальше →
Всего голосов 10: ↑3 и ↓7 -4
Просмотры 6.9K
Комментарии 6

Сокровищница отечественной криптографии

Блог компании ua-hosting.company История IT Старое железо
В своей первой статье я писала о легендарном Блетчли-Парке и криптографической службе Великобритании военного периода, о шифровальных машинах Тьюринга и немецкой «Энигма». Сейчас речь пойдет о нашей отечественной криптографии. В СССР криптография была полностью закрытой дисциплиной, которая использовалась исключительно для нужд обороны и государственной безопасности, а потому не было необходимости в публичном освещении достижений в этой области.



Попытки создания аппаратов для автоматического шифрования


Многие согласятся с американский историком Дэвидом Каном в том, что «свой современный вид шифровальное дело получило благодаря телеграфу».
Россия. Конец ХIХ века. 1879 год. Главный механик, помощник начальника Петербургского почтово-телеграфного округа Деревянкин разработал оригинальный прибор для шифрования телерамм «Криптограф».
читать дальше
Всего голосов 28: ↑28 и ↓0 +28
Просмотры 29K
Комментарии 13