fbpx

Большое количество множителей при факторизации N в RSA

245 просмотра
0

Имеется зашифрованное сообщение и модуль :

c: 9074407119435549226216306717104313210750146895081726439798095976354600576814818348656600684713830051655944443364224597709641982342039946659987121376590618828822446965847273448794324003758131816407702456966504389655568712152599077538994030379567217702587542326383955580601916478060973206347266442527564009737910
n: 18086135173395641986123054725350673124644081001065528104355398467069161310728333370888782472390469310073117314933010148415971838393130403883412870626619053053672200815153337045022984003065791405742151350233540671714100052962945261324862393058079670757430356345222006961306738393548705354069502196752913415352527

При факторизации модуля выдается 42 множителя,подумав, что перемножив 21 множителей я получу p и перемножив остальные получу q, далее раз нету открытой экспоненты, я создал список экспонент с условием, что e (1 < e<(p-1)(q-1)), далее вычислив d, попытался расшифровать сообщение, но успехов не было, сделав факторизацию через, другой сервис получил четыре значения которые по формуле суммы квадратов возвращали исходный модуль n = a^2+b^2+c^2+d^2, но взяв по принципу p = a^2+b^2 q = c^2+d^2, тоже не вышло ничего, прошу не решить за меня данную задачу, а подсказать куда мыслить далее…


Добавить комментарий

1 Ответы

Python Опубликовано 25.06.2019
0

Нужно вычислить правильное φ(n), и взять стандартную публичную экспоненту (65537). Мой пример кода:

BigInteger[] factors = new[]
{
    new BigInteger(16904777),
    new BigInteger(17673199),
    new BigInteger(17730961),
    new BigInteger(17901463),
    new BigInteger(18145913),
    new BigInteger(18313601),
    new BigInteger(18646361),
    new BigInteger(19459483),
    new BigInteger(20010041),
    new BigInteger(20013121),
    new BigInteger(20197313),
    new BigInteger(20390129),
    new BigInteger(21321539),
    new BigInteger(21647243),
    new BigInteger(21891889),
    new BigInteger(22050221),
    new BigInteger(22576643),
    new BigInteger(22685197),
    new BigInteger(23554169),
    new BigInteger(24525821),
    new BigInteger(24946057),
    new BigInteger(24996157),
    new BigInteger(25671797),
    new BigInteger(25808239),
    new BigInteger(25963459),
    new BigInteger(27138691),
    new BigInteger(27289543),
    new BigInteger(27409927),
    new BigInteger(27606707),
    new BigInteger(27739163),
    new BigInteger(28863719),
    new BigInteger(29488469),
    new BigInteger(29511773),
    new BigInteger(30342329),
    new BigInteger(30580789),
    new BigInteger(31696261),
    new BigInteger(31703933),
    new BigInteger(31737131),
    new BigInteger(31881917),
    new BigInteger(33098557),
    new BigInteger(33322589),
    new BigInteger(33381329),
};
 
var phi = BigInteger.One;
foreach (var factor in factors)
    phi *= factor - 1;
 
var e = new BigInteger(65537);
var d = BigInteger.ModularInverse(e, phi);
 
var cipher = BigInteger.Parse("9074407119435549226216306717104313210750146895081726439798095976354600576814818348656600684713830051655944443364224597709641982342039946659987121376590618828822446965847273448794324003758131816407702456966504389655568712152599077538994030379567217702587542326383955580601916478060973206347266442527564009737910");
var plain = BigInteger.ModularExponentiation(cipher, d, n);
 
Console.WriteLine(Encoding.ASCII.GetString(plain.ToBytes(ByteOrder.BigEndian)));

Получается такой текст:

timctf{mUlt1_PriM3_rS4_c0ULD_B3_DAngEr0us}

Добавить комментарий
Напишите свой ответ на данный вопрос.
Scroll Up