Алгоритм RSA. Жданов О.Н - 20 стр.

UptoLike

ВУЗ: 

СибГАУ | Красноярск

Составители: 

Рубрика: 

20
3. Вычисляем w
1
= t
1
^2 – N. Для этого A:= t
1
^2, B:= –N, затем нажимаем
«D = A + B» => D = w
1
= 5449413585028470761194878510374038309424567072020440 513
82994789890021024276071841015374407292734855936947310698222919658747488308126054
59820304360646571029919824563938405406681673931506465324109089720970066524525646
36364951379382559305195761133559499735259247329488800850465292905881621071056452
80840361927828.
4. Проверяем, является ли w
1
квадратом целого числа: A:= w
1;
B:= 2, нажи-
маем «D = A^(1/B)» => в первой строке таблицы – сообщение «[error]», следова-
тельно проделываем п. 2 заново с новым значением t
2
= n + 2 и так далее, пока
не найдем, что некое w
i
является квадратом целого числа.
5. При вычислении квадратного корня w
3
первая строка таблицы остается
пустой, а D = sqrt(w
3
) = 399601734952058738061666 3751263297399552892968316884533
40784373593737371426341961186213257189977786709916491244309450739058359801507236
75832178193635675730, что свидетельствует об успехе факторизации.
t
5
= 2629685268160267362326360511894598743824465191489636176290272551047699
45719755984982102707120117706525064015257076350250162229292374187259939548939791
85887847447050668548067978218010019841994830294453462655722503773598847602485709
2410886712781755069275022931765360611959811514005518017111151102378643337276269.
6. Вычисляем p = t
3
+ sqrt(w
5
); A:= t
3
; B:= sqrt(w
3
).
Нажимаем «D = A + B» => D = p =
262968526816026736232636051189459874382
44651914896361762902725510476994571975598498210270712011770652506401525707635025
01622292923741872599395489397918588385142970114796068736155425875654459527740148
51457711890959298629102287714458214768091456036071496351940116236181014737608169
537866387475270200449701600539;
q = t
3
– sqrt(w
3
) = 262968526816026736232636051894598743824465191489636176290
27255104769945719755984982102707120117706525064015257076350250162229292374187259
93954893979185891843464400189135448594881761283139394383187421779540255911617334
78497619997266070053341074740670536939234144850429048854198414981678348269345568
36972951999.
7. Вычисляем Phi(N) = (p – 1)(q – 1).
A:=
26296852681602673623263605118945987438244651914896361762902725510476994
55719755984982102707120117706525064015257076350250162229292374187259939548939791
85883851429701147960687361554258756544595277401485145771189095929862910228771445
8214768091456036071496351940116236181014737608169537866387475270200449701600538;
B:=
26296852681602673623263605118945987438244651914896361762902725510476994
57197559849821027071201177065250640152570763502501622292923741872599395489397918
58918434644001891354485948817612831393943831874217795402559116173347849761999726
607005334107474067053693923414485042904885419841498167834826934556836972951998.
Нажимаем «D = A·B» => D = Phi(N) =
691524460957913726732738251979937
90915241492932448166376918269398622964367867570234227167749609782487603063343406
24277737195531464527423883329887339936050919940582934993829717424909524747198284
74075078589670734862274453160000326591774304456377502636123751623356951077611481
09796496185649768169137389070008752256476598981060706729208956175334696096688927
92140973921589850309208451062123642196546488929334018952808395566678340363116470
10551595182396506795549490371941105829837814339818401626212936221330490459000092
66416844795120665115993745440985877043246616666749519592159805682710960700930681
958448326848515244974924.
8. Вычисляем d, как обратный экспоненте e: A:= e; B:= –1; C:= Phi(N).

Страницы