кто опознает аогоритм (exponentiation?)

Hi ppl!

памагите знанием кто может..



в одной проге обнаружен след. алгоритм дешифровки, слегка напоминающий right-to-left exponentiation:



экспонента (традиционная 1001h) тестируется побитово от MSB до LSB, по результатам тестирования исполняется (насколько разобрал!) такой вот код (после упрощения)



E = B mod C;

Result = 2 ;

// инициализация





TestBit // значение текущего бита



if MSB 01

{



Result = (E*( Result - 1)) mod C

E = (E*E -2) mod C

}



if MSB 00

{

E = (E*( Result - 1)) mod C

Result = (Result * Result -2) mod C

}





возвращается, само собой, Result



напоминает RSA, да вот -1 и -2 сильно смущают..

Если кто знает, что за алгоритм реализован, подскажите за так

thanx in advance

 

cryptosearcher натравить не пробовал?

BigLib Signature Collection можно прогнать в ollydbg (Ctrl+O)

 

нулик не пропустил? традиционная - это 10001h

правильно ли я понял, что дано C и выходной Result и надо найти B? можешь привести конкретные значения?

 

ага, нолик пропустил )



ну да, типа как в РША, есть модуль С, экспонента и, само собой, результат. значения могу сбросить, если сильно надо, тока длинные они (68h).



для bogrus. сигнатуры для IDA пробовал, не опознается.

да и не должно -

похоже на самопал, high precision арифметика сделана на пасквильном vln (very large numbers), в нем нет криптофункций.



спасибо за интерес!

 

Есть кое-какие идеи. Скинь числа на relf at rambler.ru

А желательно еще и контрольный пример - например, вычисли при том же C, значение Result для B=0xDEADBEEF.

 

ooppsss

поправочка к алгоритму. каюсь, не доглядел



E0 = B mod C;

Result = 2 ;

// инициализация





TestBit // значение текущего бита, от MSB до LSB



if MSB 01

{



Result = (E*Result - E0) mod C

E = (E*E -2) mod C

}



if MSB 00

{

E = (E* Result - E0) mod C

Result = (Result * Result -2) mod C

}

 

Ну так шли конкретные числа и контрольный пример - там разберемся...

 

Похоже, это следующая штука:



B представляется как

B = D + D^(-1) mod C

и качестве результата выдается

R = D^(65537) + D^(-65537) mod C.



Эта задача не проще RSA с теми же параметрами (C,10001h) (но, возможно, и не сложнее). Легко ломается, если известна факторизация C.



Так чему у тебя равно C?

 

2 RElf

дак ить я вроде заслал на rambler? не пришло??

 

Ничего не приходило.

 

В общем, это то, что называется LUC cryptosystem, а точнее LUCRSA.

См.

Lucas Sequences in Cryptography

и

So me Remarks on Lucas-Based Cryptosystems