nuevos algoritmos de factorización de enteros para atacar rsa x

44
Nuevos Algoritmos de Factorización de Enteros para atacar RSA X Reunión Española sobre Criptología y Seguridad de la Información Salamanca, del 2 al 5 de septiembre de 2008 Hugo D.Scolnik Departamento de Computación Universidad de Buenos Aires

Upload: lykhanh

Post on 13-Feb-2017

227 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

Nuevos Algoritmos de Factorización de

Enteros para atacar RSA

X Reunión Española sobre Criptología

y Seguridad de la Información

Salamanca, del 2 al 5 de septiembre de 2008

Hugo D.ScolnikDepartamento de ComputaciónUniversidad de Buenos Aires

Page 2: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

�������������� ���� ����

�� ������������� �����

�� ���������������

�� ���������� �����������������

�� ���������

�� ����������

�� �������!�����"��� ��������� �

Page 3: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

� ��������� ���� ���������� ������������� ����

��������� ����� ��� ������������� ������ !!"�

������ �������#���������������� ��#��$

Page 4: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

������!��������#

���������� $�����������%��

& ����������� !����� ������������������������$���

� � � � � �

Page 5: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

%���� �&�����#&������� ������������'������������� �����

� �� ������ ������������������������ �������(���

��'���� � ��� ����� �����)��� ��������������

* ������+,��(������������� �������������������� ��-

.��������� ���/����0����,��������� ����������������������

������������������� ������*��� ��+ � �� ����������'���&� �

��������������������������� �����������������������)1�.-

2�����������0 �

Page 6: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

�����������1�.�

����������������� ������������� ������� ������ �

������������

�����������������������������������∅���������������� ��

�������� ����������� �∅���������� �� �����!����������

"�#�����������"�����$���������������������#����� ����%� �&�'�

(��������������������������� $����������������������� �� ���

�%� �&�'�

"������������������)��(����������������� ������������

��(����(� �� ����!����� ����������$�

"���(��������(��� �� ������(

������*������ �����#������ �$�$� ���+, ∅���������������� ��$�!�

����������� ��� �∅��������'����#������������������� ��������� �������#�����

Page 7: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

��� $����()*� ����)�����+���������������������,��������������� ��&�'� &������ ������������������������������" ���-���������� ���������&�+�"��� �������&�'-./�.

��/0��1��/�2//��0����/0�//��111��02�//�0���/��1��0�0���0�/���2�11���/���/��1/1��/�������1�2�0�0���1�01���02���0�1�1/������0�/0��/1�/�2�2��1��2//0��00��1��01����0���1����/���2�0���/��00�������/2

��+�������������#

����0�����1/2���1�1������11�1��/2/1�21��01��0//��/2�����1���/1���12����//�/��/1���������1��0����02

�2//10��1����1��������1���0�2�����20��0�12�0122�1����2������1��2/11/�0�/�1/��/��212�0�2���������0�

Page 8: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

3������� �����$������� �4��������������

()*�/���.

���/����/1��22������2�/�����011/�2�22�111��0��/���0/�0����1����1�������/�/�1�2���1��2�/�10��/�0�2/2���021�/0�1�����0�����0��1/��20/�2���2�0��/���2��12�0������2���/�/1���1��/���/�0�2�10��0����1�/2�����/���/0��/��/1�10��/�0��2���2�/�����1���2�0�����//1��102����00��1���2/��/20�/������2221����//��200���12/2�0���

Page 9: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

(���� ��������������������

{ }{ }5

5

� �

���������� !���������������$��� �.�/'�'---' �

������$�� ����$����������� ��� �67� &'� �

�� ���8�� '������������������������ !������

���9���� �����8�� &�

*�����:������

� � �

� 0 �

0 0 � 0 � �

� 0 �

� �

= ∈ =

{ }

������������������������������� !������

�����������$��� -�

������8��/ �$����� ������������ ��'����� ��

� /

� �

1

1

&� 1

∉= �

Page 10: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

2������������������������� �

������������ ��

Page 11: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

3��$���� ��� $������#

������&'����� �������

����������� �

� �

� &�∈

Page 12: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

(���� ���8�����, �������������������$����������

�����������+�����������$�� ���� �����

��/���� /& �

������� /& ��+�$�������"���������� & �

��������9������������8��

� �

� ��

� � � ��

≡� �

= ≠ ≡� �� � − �

& ��

& �

3������������������������������ & �

;<�=�������������������� ��� �$������ $����� $�����>

� �

�� �

��

��� ≡

� �=� �

� �

� �� �� �

Page 13: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

)�� --- �����������, �������?�������� ����$���������

�����, ���������������������������$�� ��'�����#

---

)�� ����� �� �

)�� ������ ��

2

2

2

2

� � �

� � �

� � �

�� 1

�� 1

αα

αα

=

� �� �� � = � �� �� �� � � � � �

� � = − � ∉� �� �

∈ � ��

$��������,$���������������'������8��$������8�

���$��� ���

� 1�

� � =� �� �

� � = ∉� �� �

Page 14: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

�� �������!������������������� �

������8��������&'�����������

���������������� �������� �

� �

� &� � &�∈ ∉

Page 15: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

� �

)�� ���� ���8��9��������������

�����8�� �$��������������������

�: $��#� �'� 0

�������������

���/���������������������@���������������� �

������������������������ &0 ��

����

�� 1

� �� �

� �

= += =

= +�������1�

��/���������

��-�����������-

��������/12

Page 16: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

� �

A����: $��#��

@��������������������������� �����

1� ��� ������������$������������ ��������$��������

&��� 2� ����+����&��� �0�

&�������,�������������!��+�������!����$��������

+���� ��

� �

= ++ +

���!��������8����������������7���,�� ������

Page 17: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

� � � �

� �

)�� - ����" �����������%��-�

)�� & � '�+ & � ����������� �

�������

&'& ��'� &' �

&���������������������

������������:�� =��������� ����������������

�$�������

� � �

� � � �

� ! � (�3 � ! � (�3 � !

=− += =

+ = � = − = +

� �!�� ��+������!�������������

�����������$�� ��������$�!9� ��-

� !+ =

����������/������3�����

Page 18: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

��������

�� ������������������������

� ��� �� � ����� ������ ������

��� ��

!����"#�"��$����$�������������"��#����"$�������"%$��&"$�' !�������%�(��"�$%��)%�������*+$�����,�$�%�-�. *��$"%�&����$���"#���"��$�

� �&�� �! � ≡

Page 19: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

/���0%���������"���)��1����"%�����$��$%�����(�*"�����1�������(��%��"�"�����#�"�"��%$����$�*������"����"$�����(�����%��$������$���"���&������������"�����"�&#"�%$�

2���"�����$���-$"���#$��$���'��%�

Page 20: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

!��%�"��������$�$��0%��� ��3���$%����� �%�� ��"%���(��%$

+����$���#�& ����������$�����������$"�� �"�"%��� .���"��$��$�� ���1��%�24�$����$����$'5 ��$��$�$

���"1���� $�%�$��(������������ 67����$����$�.����$�$($��������#������� 8(��������%��"� �"($����"

9�2�

�(����� 2���45-��� ��2�6��7�!��&��6����8/$�$5$.9������� 45���� �����������$����-�@� $���2���47� �����������$����&0��.���+������� �.0����B�����C � ����-�D��

&�4 ��8/$�$.9�!�47�4����7�����8� ��B�����C-

Page 21: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

{ }

{ }

2

� �

2

E� ����������������#

)��$���: $��� �/0��0�+��� ��� 2

/'�'�'0 �+��� ���/0��0&2� 1��������8��

& �&2� &2�

1 /'�'�'0 &2�

���"�����������8��������� ������ ����

+�$���������������

� �

&�

� !

!

&�

= == =

+ =+ =

� �

� �

����8�� &2� ���� �� � 2

&��� ��� ��//2�+��������� � 2 ����� 0����

� �

= � = += = + =

Page 22: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

� � �

� �

7����� �� �����������#

D��������8������������ ������ $�����8��

& � �$����� ��������8��������

�& �& � �$����������������������$�����& ��-

����������������������

� &� � !

� � &:� !

∈ + =

+ ∈

���������!�#

�������� ���8�� ������������$�����

�,�+��!������& �&�

?�����D������� ����!�8������������������ �)F�7D(�

�����������G�F�A)�$������ $��-

� � &� �

� � � &�

∈+ ∈

Page 23: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

� �

A����: $��#

��1��

� �H/'�I'�&�� �

&� � �&��� �&�� �H/'�I�&���

� � � &��� /� � � � � -�

� � � 2//�� � � &��� /�

&� �

��� ��� ��������������#��

3�+��+�� ��� ���

== =

+ = +=

= =

Page 24: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

4 � ��#����������)��'�������$�������5��

6 ��/ ��

��������� �9� ����� 8��$���������������"����������/

7���� ��������������������,� ���9$�� ���� ��-�������� �������8�������%����$����� ������������� ����������?�����D������$����� �������8����������� ����.��'���� $�������������"�����

Page 25: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

� �

� �

����#�

��� &� - �$����������������������+

��� & �&�� - �$�������

����������������������8�

� - �. -

� � � � � �

# � � &:� ! # � �

� � #� � � � # � � � �

≡ � = += + ∈ � = +

+ −+ + + � ∆ = = −

8��������#�����������������8��������#������������������������ ����� ������������

������� ��#�� ������� ��#�� ������������������������������������

Page 26: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

� �

�: $��#

�//2/�210'�� ��/�0���2'� 0��/0����

*��������������"�����#

&�'/'��'&2'�'���'---'&2'��'1/�

���"��� ����������8��

��/�0���2� �2 1/ ��������& �-�00-��0�

0��/0����� �� 1/ ������& 1-111-

� !

� �

! � �

= = =

= = + =

= = + =� �

����

2 1/- '��� �� 1/-

�//-2/�-210 2 ������ �-���-�10

1/�-���-�10

������8�� /-/����//2/�210

� ! �

� � #

= + = ++ − + −∆ = = =

=

Page 27: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

� �������#�����������������

���������������� ����(�����

Page 28: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

3��: $�� �� ����� &()*��/�#

��/0��1��/�2//��0����/0�//��111��02�//�0���/��1��0�0���0�/���2�11���/���/��1/1��/�������1�2�0�0���1�01���02���0�1�1/������0�/0��/1�/�2�2��1��2//0��00��1��01����0���1����/���2�0���/��00�������/2

*������ �������"�����#� �

����J���- '��� 1� ���- ��$��

�00/0��/�/��200��0/�211�11�/�2���2������/�1���2�1/��0�1�

�/���02�������/��122/1�0���021�0���/���/1/1�11/���0����0

�0/�����2�����2��0����/���/�/������222//202��0��/1�

� ! �

= = +=

12�00

1���0�����0�������1�/��

Page 29: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

92:���;

�� �<<;���< �� ����;�<����<�=��� �<�������;= <� <<=��= �;;� �;�� � �< ��<�;� � ������;���=� � =����;;�=����=����<;;=� ��=�<��;��=���<;���=;��;<;�< ���=;� <����;�����<;����������=�� �=� =<�� � ��<;���� <;�=� �� ����= ��<=< �;<���� <�<� ��;= ��� ��� ��=�;�<�==��� ����<���= � ;;��;������� �� <�==��<�����= <�

Page 30: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

*��������������"������$����()*�/��

&������0'�������'�����2��&�����1�'�������'������/�&������2'�����//'��������&�������'�������'������/�&�����1�'�������'�����1/�&�����/�'�������'������/�&�������'�����//'�����11�&�����1�'�������'������/�&�������'�������'�����1/�&�������'�������'����0�/�&�������'����2��'������/���& �9� ��8��������,���������

Page 31: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

7"$��"�����&"�

� ���/�� &�� �� &�� �/��� � �+ + = +

Page 32: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

� �

E���� ������: $��#

�/0��0���� ��//2���� �0����� != = =

0/�0�/�0���2

���/��/���12

�����1/�

�/��/����

���11��/�

��2�0��/�

3���������;�<#�=����

Page 33: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

� ����2 �/��/ ��8����� ����� � � �= + =

�� �%��������&��2'�0�'0�/��+�

�����.0/�'����������� ������!� ��������

��������8����������8��K�+�8�������

Page 34: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

� � �

��

� � �

�� � � � �

)��& ' ' �����������"����-�

������� ���

+'������� $���&��$���+�����������������$����

'����������"�����& ' ' �

3��$���������������������� ��!� �����$������#

� # �

� � #

� # �

� � � � �

+ −∆ =

= + + �

�� � � � � �

8�����������������+����������

&������� ����� ��L���������L�!�L����������L�

! # �# � � �= + +

Page 35: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

@�&����2'����0�'����0�/�#� �.����0/�

@ &����/'�����'�������#�&��'���'�����.�&����2'���2�'���11/��MN�AO�PM-@ &����/'�����'�����1�#�&��'���'�����.�&����2'���2�'���0�/��MN�AO�PM-@ &����/'�����'�������#�&��'���'�����.�&����2'���2�'�����/�-

����!� ����������������������������������$�� ����������$����������"��� �-

�������������,��&��/2'0/��'����/�-�*K���'��/2�Q ��2�.��0�/�.�0/���Q ��2��.�1-0�/.1�

��������������������'��������� �

Page 36: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

� � �

� �� � � �

�� � � � � �

������������������������������������(�� ����#

�������������"�����& ' ' ��������� ���

�+�����'������@3�& ' ' �

���!� ���� �$������������������������������������

� # �

� � #� # �

� � � � � �

+ −∆ =

= + + ���

������������������������������������*����������#

�����������������������������������������������

������������������������������������������������

Page 37: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

���������

Page 38: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

����������B$�� ���������!�C#@�&����2'����2�'������/�#� �.�������@ &�����'����/'�������#�&��'���'�����.��&���/2'���2�'�����2�/������������-@ &�����'�����'�����1�#�&��'���'�����.��&���/2'��/��'���2�/�����������-@ &�����'�����'�������#�&��'���'�����.�&���/2'��/��'���1�/�����������-@ &�����'�����'�������#�&��'���'�����.�&���/2'��/��'��0�1/�����������-

������������� ����������������������'�$�������B���������C-�

D���: $��'���"��� �����,�����&���2'�����'0�1/�� �

� �

� �9 �

���� ������$����� ���8�� �/2

.���2�M��/2�.����/�.�2-��/�.� � �

������� ���8������������

� � �δδ λ

= + +

Page 39: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

���������������������������������3���������������#

@�������������������������$���������������$���� ������� ����

��'��������L���������L�& ' ' �'����� $��8�

'�� '���&J�� ��

�� ##��

�� &� ## &� � ��∈ ∈ �& �

�����8���K����$�� ���K����$����� ������������� ��$���

���������$���� �����������������������������-

���� &�∈

Page 40: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

� �

� � �

� � �

� � � 2�

� � � 2�

����������,��������������-

D���: $���$������.��/0��0����@3���& '� '� ��.�&�'/'���

8����������

����0�+�����������@3���& '� '� ��.&�'/'��

��

�/ ��$���&��'/'

� �

� � � &� &�

# #� &�

∆ =+ = ∈ =

+ = ∈ 2��������������!�

Page 41: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

E� ����K������"��� ��������� ��8�������%�����������������'�'�'�'��$�����������+��������'�+�����$������!����

()*��/

Page 42: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

3�"$��5$�� ��%����� �����"����>

Page 43: Nuevos Algoritmos de Factorización de Enteros para atacar RSA X

.��.��&& ����� ���������� �����

7��K�����������R