View
231
Download
0
Category
Preview:
Citation preview
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
�������������� ���� ����
�� ������������� �����
�� ���������������
�� ���������� �����������������
�� ���������
�� ����������
�� �������!�����"��� ��������� �
� ��������� ���� ���������� ������������� ����
��������� ����� ��� ������������� ������ !!"�
������ �������#���������������� ��#��$
������!��������#
���������� $�����������%��
& ����������� !����� ������������������������$���
�
� � � � � �
%���� �&�����#&������� ������������'������������� �����
� �� ������ ������������������������ �������(���
��'���� � ��� ����� �����)��� ��������������
* ������+,��(������������� �������������������� ��-
.��������� ���/����0����,��������� ����������������������
������������������� ������*��� ��+ � �� ����������'���&� �
��������������������������� �����������������������)1�.-
2�����������0 �
�����������1�.�
����������������� ������������� ������� ������ �
������������
�����������������������������������∅���������������� ��
�������� ����������� �∅���������� �� �����!����������
"�#�����������"�����$���������������������#����� ����%� �&�'�
(��������������������������� $����������������������� �� ���
�%� �&�'�
"������������������)��(����������������� ������������
��(����(� �� ����!����� ����������$�
"���(��������(��� �� ������(
������*������ �����#������ �$�$� ���+, ∅���������������� ��$�!�
����������� ��� �∅��������'����#������������������� ��������� �������#�����
��� $����()*� ����)�����+���������������������,��������������� ��&�'� &������ ������������������������������" ���-���������� ���������&�+�"��� �������&�'-./�.
��/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�
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���
(���� ��������������������
{ }{ }5
5
� �
���������� !���������������$��� �.�/'�'---' �
������$�� ����$����������� ��� �67� &'� �
�� ���8�� '������������������������ !������
���9���� �����8�� &�
*�����:������
�
� � �
�
� 0 �
0 0 � 0 � �
� 0 �
� �
−
= ∈ =
∈
≡
{ }
������������������������������� !������
�����������$��� -�
������8��/ �$����� ������������ ��'����� ��
� /
�
�
� �
�
1
1
&� 1
∉= �
2������������������������� �
������������ ��
3��$���� ��� $������#
������&'����� �������
����������� �
� �
� &�∈
�
(���� ���8�����, �������������������$����������
�����������+�����������$�� ���� �����
��/���� /& �
������� /& ��+�$�������"���������� & �
��������9������������8��
� �
� ��
� � � ��
≡� �
= ≠ ≡� �� � − �
& ��
�
& �
3������������������������������ & �
;<�=�������������������� ��� �$������ $����� $�����>
�
� �
�� �
�
��
�
−
��� ≡
� �=� �
� �
� �� �� �
�
�
�
�
)�� --- �����������, �������?�������� ����$���������
�����, ���������������������������$�� ��'�����#
---
)�� ����� �� �
)�� ������ ��
2
2
2
2
�
�
� � �
� � �
� � �
�� 1
�
�� 1
�
αα
αα
=
� �� �� � = � �� �� �� � � � � �
� � = − � ∉� �� �
∈ � ��
$��������,$���������������'������8��$������8�
���$��� ���
� 1�
� � =� �� �
� � = ∉� �� �
�� �������!������������������� �
������8��������&'�����������
���������������� �������� �
� �
� &� � &�∈ ∉
�
�
� �
)�� ���� ���8��9��������������
�����8�� �$��������������������
�: $��#� �'� 0
�������������
���/���������������������@���������������� �
������������������������ &0 ��
����
�� 1
� �� �
� �
�
�
∈
= += =
= +�������1�
��/���������
��-�����������-
��������/12
�
� �
A����: $��#��
@��������������������������� �����
1� ��� ������������$������������ ��������$��������
&��� 2� ����+����&��� �0�
&�������,�������������!��+�������!����$��������
+���� ��
�
� �
= ++ +
���!��������8����������������7���,�� ������
� � � �
� �
)�� - ����" �����������%��-�
)�� & � '�+ & � ����������� �
�������
&'& ��'� &' �
&���������������������
������������:�� =��������� ����������������
�$�������
� � �
� � � �
� ! � (�3 � ! � (�3 � !
=− += =
+ = � = − = +
� �!�� ��+������!�������������
�����������$�� ��������$�!9� ��-
� !+ =
����������/������3�����
��������
�� ������������������������
� ��� �� � ����� ������ ������
��� ��
!����"#�"��$����$�������������"��#����"$�������"%$��&"$�' !�������%�(��"�$%��)%�������*+$�����,�$�%�-�. *��$"%�&����$���"#���"��$�
� �&�� �! � ≡
/���0%���������"���)��1����"%�����$��$%�����(�*"�����1�������(��%��"�"�����#�"�"��%$����$�*������"����"$�����(�����%��$������$���"���&������������"�����"�&#"�%$�
2���"�����$���-$"���#$��$���'��%�
!��%�"��������$�$��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-
{ }
{ }
2
� �
�
2
E� ����������������#
)��$���: $��� �/0��0�+��� ��� 2
/'�'�'0 �+��� ���/0��0&2� 1��������8��
& �&2� &2�
1 /'�'�'0 &2�
���"�����������8��������� ������ ����
+�$���������������
� �
&�
� !
!
&�
= == =
+ =+ =
� �
� �
����8�� &2� ���� �� � 2
&��� ��� ��//2�+��������� � 2 ����� 0����
�
� �
= � = += = + =
� � �
� �
7����� �� �����������#
D��������8������������ ������ $�����8��
& � �$����� ��������8��������
�& �& � �$����������������������$�����& ��-
����������������������
�
�
�
� &� � !
� � &:� !
∈ + =
+ ∈
���������!�#
�������� ���8�� ������������$�����
�,�+��!������& �&�
?�����D������� ����!�8������������������ �)F�7D(�
�����������G�F�A)�$������ $��-
�
�
� � &� �
� � � &�
�
�
∈+ ∈
�
�
�
� �
A����: $��#
��1��
� �H/'�I'�&�� �
&� � �&��� �&�� �H/'�I�&���
� � � &��� /� � � � � -�
� � � 2//�� � � &��� /�
�
&� �
�
��� ��� ��������������#��
3�+��+�� ��� ���
== =
+ = +=
= =
4 � ��#����������)��'�������$�������5��
6 ��/ ��
��������� �9� ����� 8��$���������������"����������/
7���� ��������������������,� ���9$�� ���� ��-�������� �������8�������%����$����� ������������� ����������?�����D������$����� �������8����������� ����.��'���� $�������������"�����
� �
� �
����#�
��� &� - �$����������������������+
��� & �&�� - �$�������
����������������������8�
� - �. -
�
� � � � � �
# � � &:� ! # � �
�
� � #� � � � # � � � �
�
≡ � = += + ∈ � = +
+ −+ + + � ∆ = = −
8��������#�����������������8��������#������������������������ ����� ������������
������� ��#�� ������� ��#�� ������������������������������������
� �
�
�
�: $��#
�//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
� ! �
� � #
�
= + = ++ − + −∆ = = =
=
� �������#�����������������
���������������� ����(�����
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�/��
92:���;
�� �<<;���< �� ����;�<����<�=��� �<�������;= <� <<=��= �;;� �;�� � �< ��<�;� � ������;���=� � =����;;�=����=����<;;=� ��=�<��;��=���<;���=;��;<;�< ���=;� <����;�����<;����������=�� �=� =<�� � ��<;���� <;�=� �� ����= ��<=< �;<���� <�<� ��;= ��� ��� ��=�;�<�==��� ����<���= � ;;��;������� �� <�==��<�����= <�
*��������������"������$����()*�/��
&������0'�������'�����2��&�����1�'�������'������/�&������2'�����//'��������&�������'�������'������/�&�����1�'�������'�����1/�&�����/�'�������'������/�&�������'�����//'�����11�&�����1�'�������'������/�&�������'�������'�����1/�&�������'�������'����0�/�&�������'����2��'������/���& �9� ��8��������,���������
7"$��"�����&"�
� ���/�� &�� �� &�� �/��� � �+ + = +
� �
E���� ������: $��#
�/0��0���� ��//2���� �0����� != = =
0/�0�/�0���2
���/��/���12
�����1/�
�/��/����
���11��/�
��2�0��/�
3���������;�<#�=����
� ����2 �/��/ ��8����� ����� � � �= + =
�� �%��������&��2'�0�'0�/��+�
�����.0/�'����������� ������!� ��������
��������8����������8��K�+�8�������
�
� � �
��
�
� � �
�� � � � �
)��& ' ' �����������"����-�
������� ���
+'������� $���&��$���+�����������������$����
'����������"�����& ' ' �
3��$���������������������� ��!� �����$������#
� # �
� � #
�
� # �
� � � � �
+ −∆ =
= + + �
�� � � � � �
8�����������������+����������
&������� ����� ��L���������L�!�L����������L�
�
! # �# � � �= + +
@�&����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�
��������������������'��������� �
� � �
� �� � � �
�
�� � � � � �
������������������������������������(�� ����#
�������������"�����& ' ' ��������� ���
�+�����'������@3�& ' ' �
���!� ���� �$������������������������������������
� # �
� � #� # �
�
� � � � � �
+ −∆ =
= + + ���
������������������������������������*����������#
�����������������������������������������������
������������������������������������������������
���������
����������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������������
� � �δδ λ
= + +
���������������������������������3���������������#
@�������������������������$���������������$���� ������� ����
��'��������L���������L�& ' ' �'����� $��8�
'�� '���&J�� ��
�� ##��
�� &� ## &� � ��∈ ∈ �& �
�����8���K����$�� ���K����$����� ������������� ��$���
���������$���� �����������������������������-
���� &�∈
� �
� � �
� � �
� � � 2�
� � � 2�
����������,��������������-
D���: $���$������.��/0��0����@3���& '� '� ��.�&�'/'���
8����������
����0�+�����������@3���& '� '� ��.&�'/'��
��
�/ ��$���&��'/'
� �
�
�
� � � &� &�
# #� &�
∆ =+ = ∈ =
+ = ∈ 2��������������!�
E� ����K������"��� ��������� ��8�������%�����������������'�'�'�'��$�����������+��������'�+�����$������!����
()*��/
3�"$��5$�� ��%����� �����"����>
.��.��&& ����� ���������� �����
7��K�����������R
hscolnik@gmail.com
Recommended