Возможно ли восстановить криптоалгоритм по данным?

[rerime]

Есть некий алгоритм, который преобразовывает данные в левом столбце в данные в правом столбце соотвественно. То есть каждой строке слева 20 символов (hex) или 10 байт преобразуются справа в 20 символов.
Вопрос можно ли по данным восставить алгоритм преобразования?
Поскольку длина сохраняется возможно применяется нечто похожее на
http://en.wikipedia.org/wiki/Format-pre ... encryption

FFFFFFFFFFFFFFFFFFFF 81DC79B960AA2A0CA4EF
81DC79B960AA2A0CA4EF 44D9CDE81BB3DA1CE972
082F72982AA853C73DD1 CA60E087CF49D88600B5
4D7EE36CA5F81E13A316 E2FB5EBF4BA02F3B3227
FA8BEFA2C16D94039DF2 C885367260066297D57A
FF17B926532FAA1D144B BC67B934CEACF81F8D08
CB6C128C59843394A994 292582948504F63A514B
E974E24A5669D47174EF 7AFE0EC4D430C189D31F
FA8B09B9CBD9DCD2E1AA 01A2CF1EE67F794457E1
ECE7FC3780B550876421 A7219E404A4B50885A9A
F17308C560FDCB66FBA3 CECD3E90FA7180C64E48
F1736935D0FDFF4D8478 BF5E6631D2ECA9944EAB
ECE765F0068DCC46502E 9E061AE51D9D786BC0A2
1EEB08FC0A711C3263B3 D061E78BAEC3568519DC
F1730192E8F5D5BEB2C1 8BAF4C4E0C140F50DBF8
E85BC6E5E80E3E215273 712B6AB7CAF681739E2E
5C35108E739D4C4877C0 42B18C11D80558B1E562
F1730DFE86D7A2A817E8 B7FFDDCA6EEA478621FD
F5FF3C3803F622EDDAF2 564C869B73399525DC0F
E5B9CE9CF03D7D9B5C53 8205416DCE434D7B332A
D0071C149A6057B9DA82 484D5C121E40A4BDCBBA
E85B1195361AFD05617F EE176AA27F57037E233A
3AABF81916E152107FE2 C31CFD9F048509594B8D
B591D08667A39179CCB3 315903F904A3D72D0074
F1732967F590D3C68FB0 F3FD26ED3F68EA9617EB
A9316387B68CA3BBD025 8509024B9C34227136B9
F5FFF7919265500CD5FD B03C16385D87BF29CDD9
F5FFE42978AFE0AB539B BD97475C1C083CBB33FD
F5FF95B6EAE252A866C1 615FF65B6B5281D1CF82
E32D7D819D15FD8508A1 7335D0E970E77EBB349B
ECE7AB3D0615645733D4 A4C3939A88117DD6FBC4
4C643F933F5069AD0943 1C028439CFE9FD610DC9
FA8B7B34A33DB9BB7B7F AF4F77C8F3C38C8CD554
03A30F73EA8708CB8A89 3E64D85507570D5B83FB
FA8B4A820CEDF282A8C0 4D85D0F968F77D94FF86
5C22452FC03F91182FFB 56E75FCA742F7EDB47C8

[arseniiv]

rerime в сообщении #968382 писал(а):

Вопрос можно ли по данным восставить алгоритм преобразования?

Вы же понимаете, что нет. Сколько входных строк возможно — и сколько тут приведено?

[rerime]

Ok, а если есть возможность все возможные варианты строк пропустить через алгоритм? Не хотелось бы конечно это делать может есть некий разумный минимум. Плюс у меня подозрение, что это может быть какой-то известный алгоритм.

[arseniiv]

Известный алгоритм с неизвестными параметрами.

Вообще, конечно, у известного алгоритма могут найтись какие-то свойства, позволяющие подобрать параметры по относительно безобидному числу пар… для каждого свои. Может, кто-то и захочет тут все эти альтернативы перечислить.

rerime в сообщении #968395 писал(а):

все возможные варианты строк

Все в данном случае не стоит и думать: их порядка $10^{24}$; даже если получать по $10^{12}$ пар в секунду, всё займёт около 30 тыс. лет.

-- Пн янв 26, 2015 02:59:31 --

arseniiv в сообщении #968422 писал(а):

Может, кто-то и захочет тут все эти альтернативы перечислить.

Или посоветуют где быстрее найти. Надеюсь.

[rerime]

Остается надежда по каким-то характерным особенностям найти алгоритм, иначе мне видится задача нахождения сразу некого преобразования являющимся алгоритм-ключ, потом вычленения алгоритма...
Нет, если обоснуют, что задача не решается за разумное время тоже хорошо)

[Henrylee]

Ну если предполагать, что это некий симметричный шифр, то, видимо, криптографическое преобразование будет комбинацией простых подстановок, перестановок и гаммирования (сложения по модулю, $16$, конечно же). Можно начать с предположения, что имеем дело с потоковым шифром (символ заменяется на символ). Гаммирование в чистом виде, конечно, нет. Замены тоже. МОжно попробовать их комбинацию. Типа составной шифр Виженера. Ну и т.д.

[Sonic86]

rerime в сообщении #968395 писал(а):

Ok, а если есть возможность все возможные варианты строк пропустить через алгоритм?

Если программа детерминированна, т.е. если это реально алгоритм, то восстановить некоторую программу, вычисляющую функцию, очевидно можно.
Т.е. если мы знаем, что $f: f(x_j)=y_j$ для $j=1,...,n$, то программа

int Func(int x){
  if(x=x_1){
    return y_1;
  }
...
  if(x=x_n){
    return y_n;
  }
}

является одной из искомых.
На самом деле клиент конечно же хочет получить не эту программу, а ей эквивалентную, но более короткую и читабельную (хотя в явном виде это не сказал, ибо это клиент, ему главное вовремя выполнить задачу перед начальством). Однако, класс эквивалентных программ, очевидно, счетен по мощности, а кроме того, зависит от синтаксиса языка. Т.е. на самом деле задача имеет вид: дан текст программы, надо его максимально упростить и сделать понятным для человека. Однако, максимальное упрощение сродни поиску колмогоровской сложности, которая, как известно, невычислима. Кроме того, учет т.н. человеческой логики чревато некрасивостью программ. В результате нам на самом деле нужно суметь поставить задачу корректно, после чего уже пытаться решать ее. Нам надо ограничиться неким явным синтаксисом программ, а также явно задать на классе эквивалентных программ достаточно простую функцию упрощения, близкую к оптимальной, но не оптимальную. Последнее - не самая тривиальная задача, причем уже из области формальных грамматик, тут думать надо.
Еще одним подводным камнем работы с клиентом является тот факт, что после самостоятельного переосмысления задачи следует отдать переосмысление клиенту на подтверждение. Часто клиент после подтверждения в ужасе сильно меняет исходную постановку задачи. Например так: дана неизвестная $f$ и известные $f_1,...,f_m$, где $m$ мало. Надо найти $j: f=f_j$ или показать, что такого $j$ нет.

[rerime]

Sonic86

Цитата:

Т.е. если мы знаем, что $f: f(x_j)=y_j$ для $j=1,...,n$, то программа

Естественно эта программа абсолютна неприемлема, поскольку подразумевает под собой размер 16^20 блоков if.
Вопрос как упрощать...
А как найти эти простые перестановки и гаммирования. Вычисления же проходят в двоичной системе наверное тогда гаммирования по модулю 2?
Шестнадцатиричное это же для удобства представления или это будут абсолюто идентичные операции?


Дополнение:
00000000000000000000 1E791844BAB6796ABE28
11111111111111111111 70E86CE1AB895100F0C5
22222222222222222222 DECF29F5F4CF3E8106CE
33333333333333333333 0F5390D6F00B1F02A5AA
44444444444444444444 1746AAF7485C618A5E07
55555555555555555555 B0A74ABA90FBEE1F45A2
66666666666666666666 CE2F8E4FC93B6DB33219
77777777777777777777 483960BC06F061F7303B
88888888888888888888 12988A54E16C9294C114
99999999999999999999 98CD9B9A68E3C29BA72D
AAAAAAAAAAAAAAAAAAAA 33E0DEA25EF555D60336
BBBBBBBBBBBBBBBBBBBB 05B29102B5FF447C3810
CCCCCCCCCCCCCCCCCCCC E3293E30596D67275AF8
DDDDDDDDDDDDDDDDDDDD D2079681FEFB93931497
EEEEEEEEEEEEEEEEEEEE C84DF47E69322CD262F8
00000000000000000001 AB5C4EB0B6208362D6F7
00000000000000000002 E5F01580480B40C8DE6C
00000000000000000003 65721189D3A6BAD9C1F7
00000000000000000004 CF0F6D6780F822338654
00000000000000000005 D8A3973F5FC12958F577
00000000000000000006 02B8DBEBEFA6AEEB13AF
00000000000000000007 51C80D4DAC4A8BC42BAD
00000000000000000008 F79FDFD86D76725F36DB
00000000000000000009 2C24C1C97B0BA29FF5D8
0000000000000000000A CACC5F86D36E5F9B642F
0000000000000000000B 0D23F67AB74C05B7C3BE
0000000000000000000C 62C4F7277636FE53A130
0000000000000000000D BAE2E4DA6931E4D2D74C
0000000000000000000E FE10330128651B73F461
0000000000000000000F 83E59E8D884BC4C9FA84

[Sonic86]

rerime в сообщении #968526 писал(а):

Sonic86

Цитата:

Т.е. если мы знаем, что $f: f(x_j)=y_j$ для $j=1,...,n$, то программа

Естественно эта программа абсолютна неприемлема, поскольку подразумевает под собой размер 16^20 блоков if.

А почему этого условия нет в исходной постановке задачи?
Повторюсь: пока задачу формально полностью не поставите, вменяемого решения не получите.

rerime в сообщении #968526 писал(а):

Вопрос как упрощать...

А я уже писал:

Sonic86 в сообщении #968506 писал(а):

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

Вы можете на месяц примерно забыть про написанные зеленым текстом входы и выходы, поскольку Вам до них идти еще далеко - сначала придется разбираться с грамматиками.
Вам ответ понятен? Или мне тему можно не читать, чтобы свое время не тратить?

upd: а, простите, я туплю: Вам arseniiv уже все написал же...

[Xaositect]

А с помощью чего Вы эти пары получаете? Может, легче внутрь посмотреть?

[rerime]

Нам не нужно разбираться грамматиками и объявлять синтаксис. Задача в прямом смысле определелить какой был применен алгоритм из существующих, например это хэш вычисляется MD5 (естественно это не MD5). Отсюда у меня вопрос возможно ли это...
Нужен опыт человека связанного с криптографией, может быть по каким-то характерным особенностям можно это понять.

[Sonic86]

rerime в сообщении #968628 писал(а):

Нам не нужно разбираться грамматиками и объявлять синтаксис.

Ага, смешно. Тогда я сюда последний раз пишу.

rerime в сообщении #968628 писал(а):

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

А Вам известно множество существующих алгоритмов? А Вы в курсе, что они параметрические? А если $f$ - существующий алгоритм, $g$ - какое-нибудь тривиальное сложение с константой по модулю $2$, константа зашита в код, то шифрующие алгоритмы $f\circ g, g\circ f$ является известным или нет? А Вы знаете, насколько много можно таких простеньких $g$ добавить?

И т.д. И т.п.

(Оффтоп)

предрекаю теме 5 страниц, причем клиент будет сообщать по одному новому условию на каждой странице