LINUX.ORG.RU
ФорумTalks

[криптография]Новый (?) алгоритм шифрования

 


0

1

Как известно, задача разложения числа на простые множители является вычислительно сложной, по крайней мере на настоящий момент — значит её можно взять за основу.

Кроме того любое число несёт в себе информацию. Исходя из этих двух идей, довольно легко придумать алгоритм шифрования:

1) Исходные данные представляются в виде двоичного кода (например, если это русский текст, то можно закодировать его по ГОСТу (iso8859-5), что бы занимал меньше места. 2) Текст разбивается N примерно равных частей по M бит. M должно быть достаточно большим, например, не менее 4096 (т.е. 512 байт). Для небольших текстов желательно взять две части. Это можно делать например командой split 3) Части интерпретируются просто как числа:

echo -n "какая-то фраза" | xxd -p -u # шестнадцатеричный вид
echo -n "какая-то фраза" | xxd -p -u | tr -dc 0-9A-F | dc -e16i?p # десятичный вид

Как пример: есть abc — в ASCII это \x61\x62\x63 А значит число будет 0x616263 или 6382179.

3.5) Шаг опциональный — для простого текста его можно не делать — каждый кусок текста оформляется таким образом, что бы к нему добавился номер и, например, маркер конца строки.

4) Теперь у нас есть N чисел. Далее, надо каждое из них превратить в простое. Для этого я предлагаю приписывать к ним от 0 до d цифр, где 0 цифр нужно, если случайно окажется, что число уже простое. А конкретные цифры, которые нужно приписать к числу находятся перебором. Цифры к числу приписываются обязательно слева: Bn=An*b^d+D — где D подбирается так, что бы число Bn было простым, а b — основание системы счисления (например 10, 16 или 256). При этом, подбирать придётся, скорей всего, не так уж и долго.

5) Все полученные числа перемножаются.

6) Полученный результат для удобства следует представить в виде печатных знаков, например с помощью base64:

$ echo 1254542325621 | dc -e ?P | base64
ASQYjLd1

Шифротекст готов. Кстати, я тут попробовал этот алгоритм применить вручную. Попробуйте расшифровать:

F2by3fRqZDAzNocxFDcKvU9wRhELEcrP/HMmN/KPhmwh6x43OpW3p55W+UjxZybvCki1sQhMUfmbDiL9fhVygQ==

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

Кстати, о применении: 1) Классическое шифрование — в качестве ключа случайное число, которое просто умножается на открытый текст. 2) Хеширование — взять последние несколько байт полученного составного числа 3) Например, вы не хотите светить свои личные данные, но хотите иметь возможность доказать, что это вы в случае чего (например восстановление пароля на сайте). Для этого нужные данные (например email-адрес) дополняются мусором и шифруются моим алгоритмом. Полученный результат отправляется на сайт. Далее, если вам понадобится восстановить аккаунт, можно отправить админу сообщение с нужного e-mail, содержащее один из простых множителей — админ делит шифротекст на него, получает результат и убеждается, что он совпадает с адресом, откуда отправлено письмо — тогда он высылает на этот адрес новый пароль. Можно использовать для этого и что-то другое, например md5 от e-mail-адреса с солью, но это менее надёжно, так как в принципе возможны коллизии. Мой алгоритм по сравнению с алгоритмами хеширования всегда гарантирует принципиальную возможность получить исходный текст полностью. (по крайней мере, если добавить способ отличить кусок текста от D)

Правда, этот алгоритм имеет некоторую уязвимость — если знать часть исходного текста и шифротекст — восстановить остальное становится проще (А если знать (N-1)/N теста — можно восстановить 1/N вообще без усилий).

★★★★★

Последнее исправление: Xenius (всего исправлений: 3)

Ответ на: комментарий от Yareg

Хэш какой-то...

В хеше могут быть коллизии — в отличии от хеша, если использовать мой алгоритм с некоторым дополнением (например фиксированная длина частей в битах или маркер окончания части) — их быть не может

Xenius ★★★★★
() автор топика
Ответ на: комментарий от abraziv_whiskey

Хэш в том смысле, что обратно-то как?

Разложить шифротекст на множители, сконвертировать числа в строки (dc умеет), выкинуть D (используя маркер конца строки, если нужно), склеить по порядку (использовать при необходимости маркер порядка)

Xenius ★★★★★
() автор топика
Ответ на: комментарий от Xenius

А как разложить? Если ты в начале сказал, что это сложная задача?

abraziv_whiskey ★★★★★
()

довольно легко придумать алгоритм шифрования

Да придумывать-то их легко...

Igron ★★★★★
()

Прекрасная картина — велосипедостроитель в порыве вдохновения. Да, шифр очень криптостоек — его не получится расшифровать даже при наличии ключа. Впрочем, не следует пользоваться одним и тем же ключом дважды — в таком случае он-то как раз будет тривиально получаться при помощи алгоритма Евклида. Автору срочно нужно почитать какую-нибудь умную книгу, дабы посеять в себе зерна разумного, доброго, вечного. Например, Шнайера.

trycatch ★★★
()

Спать надо в такое время.

А теперь придумай алгоритм расшифрования.

unC0Rr ★★★★★
()

если это текст, то можно закодировать его по <вставить_здесь_национальную_кодировку>, что бы занимал меньше места

И сразу фтопку.

Suigintou ★★★★★
()

Ужасно. ТС, не пытайся больше заниматься криптографией, это явно не твое.

Manhunt ★★★★★
()

Переводим текст на какой-нибудь навахо и записываем его китайскими иероглифами :)

Eddy_Em ☆☆☆☆☆
()

Как известно, задача разложения числа на простые множители является вычислительно сложной

Очень, очень большого числа специального вида

vasily_pupkin ★★★★★
()

Далее, надо каждое из них превратить в простое. Для этого я предлагаю приписывать к ним от 0 до d цифр, где 0 цифр нужно, если случайно окажется, что число уже простое. А конкретные цифры, которые нужно приписать к числу находятся перебором. Цифры к числу приписываются обязательно слева

Признаки делимости не изучали? Вы можете сколько угодно цифр к 25 слева приписать, оно простым не станет.

buddhist ★★★★★
()

Я предлагаю ничего не умножать. Просто заменить весь текст на рандомные значения.
Криптостойкость 100%.

Galant
()

Самый стойкий односторонний крипто-алгоритм в мире

0

Расшифруй!

iBliss
()

Попробуйте расшифровать: F2by3fR...

«Штирлиц был уверен: шифровку невозможно расшифровать потому, что это был его личный шифр» (с) Штирлиц :)

quickquest ★★★★★
()

M должно быть достаточно большим, например, не менее 4096 (т.е. 512 байт)
Теперь у нас есть N чисел. Далее, надо каждое из них превратить в простое

Да как два пальца, чо. Тут как раз рядом квантовый компьютер обсуждают.

note173 ★★★★★
()
Ответ на: комментарий от Eddy_Em

Шифр из разряда «XOR с содержимым /dev/urandom»

При необходимости, вскрывается. Генератор из /dev/urandom хлипенький, и в мануалах неоднократно говорится не использовать его в криптографии.

segfault ★★★★★
()

Знавал я одного профессора в области теории кодирования, который на старости лет решил залезть в криптологию со своими поделками. Предлагал асимметричный алгоритм шифрования, требующий общий закрытый ключ. При этом использовал только линейные преобразования. Но у него данные хотя бы восстанавливались при наличии всех ключей. Я и не думал, что увижу более феерическую чушь! Спасибо, ТС.

segfault ★★★★★
()

А конкретные цифры, которые нужно приписать к числу находятся перебором. Цифры к числу приписываются обязательно слева: Bn=An*b^d+D

d больше длины D или не обязательно?

cvs-255 ★★★★★
()
Ответ на: комментарий от xapienz

там написано «привет, лор»

Не угадал.

Xenius ★★★★★
() автор топика
Ответ на: комментарий от stolz

Почти. :) Первое правило шифровальщика: никогда не изобретать новый алгоритм шифрования.

Ну если я его буду использовать на практике, то вначале я буду шифровать, например, AES, а потом уже своим алгоритмом.

Xenius ★★★★★
() автор топика
Ответ на: комментарий от buddhist

Признаки делимости не изучали? Вы можете сколько угодно цифр к 25 слева приписать, оно простым не станет.

Это я как раз изучал, просто перепутал лево и право... Но в формуле-то всё правильно.

Xenius ★★★★★
() автор топика
Ответ на: комментарий от cvs-255

d больше длины D или не обязательно?

Да, d больше длины D, иначе число D, которое может быть любым, затрёт последние байты.

Xenius ★★★★★
() автор топика
Ответ на: комментарий от segfault

Генератор из /dev/urandom хлипенький, и в мануалах неоднократно говорится не использовать его в криптографии.

Точно (сам же писал об этом)!

/dev/random надо

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Eddy_Em

Да, но после второго XOR'а половина тех символов, что инвертнулись при первом, инвертнутся обратно и снова станут корректными. Это все равно что сксорить обе гаммы между собой (хотите сказать, у результата нулями будут только 25% бит?) и наложить на открытый текст.

segfault ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.