숫자 알파벳 암호 - susja alpabes amho

�˱� ���� ��ȣ �̾߱�

        Windows 95/98/NT/2000/XP, Netscape Navigator, Lotus Notes�� ����Ͽ� ���� OS, ����Ʈ��� ���ǰ� �ִ� RSA ����Ű ��ȣ �� �����Ӱ� ����� �� �ִ� PGP ��, �̷��� ����� �̷�� �ִ� ���� ���� ���μ����ض�� �� �� �ִ�.

1. ������ȣ(������ ��ȣ�� �����ȣ, ���Ű ��ȣ, ����Ű ��ȣ)

        ���� ��ȣ�� ������ ��ȣ������, ���� ��ȣ�� ����� �����ϴµ� ���� ���̴�. ���� ��ȣ�� �θ� Ȳ�� �ٸ�� ������ ����ߴ� ��ȣ�̴�. ������ �����Ͽ� ���ĺ��� ��� ��(�Ǵ� Ű ��)��ŭ ����Ʈ ���� ����Ѵ�. ���� ���,

THE DAZED BROWN FOX QUICKLY GAVE JUMPS

��� ��(��ȣȭ�DZ� ���� ����)�� 3���ھ� ����Ʈ ���� ��ȣȭ��Ű��

WKH GDCHG EURZQ IRA TXLFNOB JDYH MXPSV

�� ���� �ǹ� ���� �������� ��ȯ�ȴ�. �׷��� �ؼ��� �����ϱ� ������ ���� �� ������ �����Ͽ� ������ ���� ����ϴ� ���� ���� ���̴�.

WKHGDCHGEURZQIRATXLFNOBJDYHMXPSV

��ȣȭ(��ȣ���� ������ �ǵ����� ��) ����� �ܼ��Ͽ� 3���ڸ�ŭ ������� �ǵ����� ������ ���� �ȴ�.

THEDAZEDBROWNFOXQUICKLYGAVEJUMPS

������ ������ �����̹Ƿ� �ܾ��� ������ ����� �� �� ������, �����ܺ��� �ǹ� �ִ� ���� ������ ó���� �ϰ� �Ǹ� �ᱹ ������ �ľ��� �� �ִ�. �� ������ ��ȣ�� Ǫ�� Ű�� 3�̴�.

�׷��� ���ĺ��� ��� 26�ڷ�, Ű�� �־��� 3�̶�� ���ڸ� ���� 1, 2, 3, 4, 5����� ������� Ǯ����� �ᱹ �ǹ� �ִ� ���忡 �����ϰ� �ǹǷ� �ص��� �����ϴ� ���� �� �� �ִ�.

��ȣȭ�� ������ �Է��ϸ�, 1, 2, 3����� ������� �����Ͽ� ���� ������ ��ϵ� �ܾ�� ���Ͽ� �ǹ� �ִ� ������ ����ϴ� ���α׷��� �ۼ��� �� �ִ�.

�׷��� �� ����� ���� ���ͳ����� ��ǥ�Ǵ� ��Ʈ��ũ ȯ�濡���� �Ҹ��ϴ�. �ᱹ

(��) ����� ���ϴ� ����� ����ŭ key�� �ʿ��ϰų�,

(��) ��ȣ ����� �˸� ��ȣȭ ����� �巯����.

��ȣ�� �翬�� ���� �� �ܱ� � �����Ǿ� ���Ǿ� �Դ�. �׷��� ��Ʈ��ũ�� �ߴް� �Բ� �Ϲ��ε� ���ͳ� ������ �� ��, �ſ�ī�� ��ȣ�� �۽��� ������ ��쿡�� ����� ����� Ȯ���� �ʿ䰡 �־� ��Ʈ��ũ�� ���ؼ��� ��ȣ�� ���ǰ� �Ǿ���.

��Ʈ��ũ ȯ�濡���� ���� ���ѵ� ����ڻӸ� �ƴ϶� ��Ư�� �ټ��� ����ڵ� �����Ѵ�. ���� ��ȣ�� ����Ͽ� ����� �Ϸ��� ��� ����ڰ� ���� ��ȣȭ Ű, ��ȣȭ Ű�� �����Ѵٴ� ����, ��Ʈ��ũ�� �����ϴ� ��� ����ڰ� ���� ����� �ϱ� ���ؼ� ����� ������ Ű�� �ʿ��ϰ� �ǹǷ� �ǿ������� ���ϴ�. ���� ��ȣȭ ����� �˸�, ��ȣȭ ����� �ľ��� �� �����Ƿ� ������ ������ Ÿ���� ���¿��� ���� �����ϴ� ���� ���˿� ����DZ� ����. �̷��� ������ �����ϱ� ���� ���ȵ� ��ȣ�� ����Ű ��ȣ��� �� �� �ִ�.

2. ����Ű ��ȣ(���ο� ��ȣ)

        1976�� �������� ������ Diffe, Hellman�� ����Ű ��ȣ�� ������ ��ǥ�Ͽ���. ����Ű ��ȣ�� �ڽſ��� �������� �޽����μ� ��ȣȭŰ�� ����ϰ� �����Ѵ�. �̷��� ��ȣȭŰ�� ����Ű�� �θ��� å���� Ȯ���� ���(���� ��� ������������ ���� ���)���� �����Ͽ� ������ ������ �� �ֵ��� �Ѵ�. �̿� ���Ͽ� ����Ű�� ������ �޽����� �ص��ϱ� ���� ��ȣȭŰ�� ���Ű��� �Ҹ���. ���Ű�� �ڱ� �ڽŸ� �ƴ� Ű�̴�. �̷��� �ϸ� ��� ������� �ڽŸ��� �ƴ� ���Ű�� �ϳ��� ������ ������ �ȴ�. ��Ʈ��ũ�� �����ϰ��� ������ ����Ű�� �����Ͽ�, �� Ű�� ��ȣȭ�� �޽����� ������ ������ ����� �����ϰ� �ȴ�.

�׷��� ���� ��ȣ������ ���� ������ ������δ� ��ȣȭŰ�� �˰� �Ǹ� ��ȣȭŰ�� �巯���� �ǹǷ� ������ ������ �߻��ϰ� �ȴ�. ���⼭ ��ȣȭ�ϴ� Ű�� �˾Ƶ�, ��ȣȭ�ϴ� Ű�� �ص��ϴ� ���� ���� �Ұ����� "�Ϲ�����"�� �Լ��� �ʿ��ϰ� �ȴ�. �̷��� "�Ϲ�����"�� �Լ��μ� ���μ� ������ ���� �� �� �ִ�.

3. ����

        �׷��� ����Ű ��ȣ������, ������ �ڽſ��� �޽����� ������ ��, Ű(����Ű)�� �����ϰ� �����Ƿ� �����̶�� ������ �ʿ��ϰ� �ȴ�.

���� ���, ���л� �ﵹ�̰� ����̿��� �� ������ �����ϱ� ���Ͽ� ���ͳ� ���Ÿ� �ϰ��� �Ѵ�. �׷��� ���� �����Ͽ� ¦�� ������ �ֹ��Ϸ��� ���� ��, �ٸ� ������� �ֹ� ������ �˷����� �β����� ��ȣȭ���� �ֹ��� �Ϸ��� �Ѵ�. ���⼭

"�ַʵ��� �ﵹ�̶�� ����ε�, ¦�� ���� �ϳ� ��Ź�մϴ�."

��� �޽����� ���θ����� �����ϰ� �ִ� ����Ű�� ��ȣȭ���� �۽��Ѵ�. �׷��� �̰͸����δ� �����ϴ�. ����Ű ��ȣ������ ��ȣȭ�� ���� Ű(����Ű)�� �����ϰ� �����Ƿ� ������ �� �� �ִ�. ���� �ﵹ�̰� �ƴ϶� �ҵ��̵�

"�ַʵ��� �ﵹ�̶�� ����ε�, ¦�� ���� �ϳ� ��Ź�մϴ�."

��� �޽����� ���θ��� ����Ű�� �̿��Ͽ� �ֹ� ������ ��ȣȭ���� ���� �� �ִ�.

�׷��Ƿ� �� �޽����� �ﵹ�̶�� �Ǿ� �־ ������ �ﵹ�̰� ���� �ֹ��� ���̶�� ���� Ȯ������ ������ �� �ȴ�. ���� �ﵹ�̴� ���Ű�� �̿��Ͽ� ������ ���� 2���� �޽����� ���� ���ۿ� ����.

�� ���ַʵ��� �ﵹ�̶�� ����ε�, ¦�� ���� �ϳ� ��Ź�մϴ�.�� ��� �޽����� ���θ����� �����ϰ� �ִ� ����Ű�� Ű�� �Ǵ�.

�� ������ �ﵹ�̶��ϴ�.�� ��� �޽����� �ﵹ���� ���Ű�� Ű�� �ɰ�, �������� ���θ��� ����Ű�� �ٽ� �� �� Ű�� �Ǵ�.

�������Ƿ�

�� ���θ��� ����Ű �����ַʵ��� �ﵹ�̶�� ����ε�, ¦�� ���� �ϳ� ��Ź�մϴ�.����

�� ���θ��� ����Ű ���ﵹ���� ���Ű�������� �ﵹ�̶��ϴ�.������

�ᱹ�� ������ �ﵹ�̶��ϴ١���� �޽����� �������� Ű�� �ɰ� �ִ�. �޽����� ���� ���� ���θ��� ���θ��� ���Ű�� �޽����� ���� ����.

�� ���ַʵ��� �ﵹ�̶�� ����ε�, ¦�� ���� �ϳ� ��Ź�մϴ�.��

�� �ﵹ���� ���Ű �������� �ﵹ�̶��ϴ�.����

��� �޽����� �� �� �ְ� �ȴ�. �׷��� ������ �ﵹ�̶��ϴ�.����� �޽����� �� �������� �ﵹ���� ���Ű�� �ѷ��ο� �����Ƿ� �ǹ� �Һи��� �޽����� ���� ���̴�. �׷��� �� ���� �޽��������� ���ַʵ��� �ﵹ�̶�� ����ε�, ¦�� ���� �ϳ� ��Ź�մϴ�.����� �Ǿ� �����Ƿ� ���θ��� �ﵹ���� ����Ű�� �ǹ� �Һи��� �޽����� �����. �ᱹ ���θ��� ������ �ﵹ�̶��ϴ١���� �޽����� Ȯ���ϰ� �ȴ�. �ﵹ���� ���Ű�� ���θ� �˰� �����Ƿ� �и��� �������κ����� ���� �� �޽������ ���� Ȯ���� �� �ִ�.

4. �������

        ���μ����ش� �̹� �˰� �ֵ���

�� ���� �� �� �ִ�. �̷��� ���� ��ȣ �̷��� �ٰ��� �̷� �� �ִ��� �ǹ��� ���� ���̴�. �׷��� �� ������ ���μ� ���ذ� �����ϰ�����, �ڸ����� 200���� �Ǹ� ���μ����ذ� �׷��� �������� �ʴ�.

�׷�, ��������� 1, 2, 3, 4������ ������ ���� �ʰڴ°�?�� ��� ������ �� �ִ�. �׷��� 200 ������ �ڸ����� ������ ���ڸ� ���μ������ϸ� ���� �ְ����� ������ǻ�͸� ����Ͽ��� ���ʾ� �� ���� �ҿ�Ǿ� ���������� ���ϴ�.

�Ҽ��� 2 �ܴ̿� ��� Ȧ���̹Ƿ� ��2, 3, 4, 7, 9, 11, 14������ ���� 2 �̿ܿ��� 2�� �dzʶٸ� ������ �Ǹ� ����� ȿ���� �� ��� �þ ���̴�. �׷��� �̷��� �Ͽ��� ���ʾ�� �ɸ��� �ð��� �������� �پ� ��� �޶��� ���� ���� ���̴�. ����� �ɷ� ��ȣ�� �ص��ߴ� �Ͽ��� �� �����̸� �ص��� ��ȣ�� �ǹ̰� ���� ���̴�.

��ü�� ������ �������, ���� 200 ������ �ڸ����� ������ ���ڶ�� �ص� �Ҽ����� �ƴ��� ������ ���� �ܽð� ����(5������) ȿ�������� �Ǵ��� �� �ִ�. � ���ڸ� �����Ͽ��� ��, ���Ҽ��� Ȯ���� 99.9999999%����� ���ڰ� �ִٰ� ��������.

���� ���ڴ� Ȯ���� �����Ƿ�, �翬�� �Ҽ��� ���̴������ �����ϴ°�? �ƴϸ� �������� ����� �߸��� ������ ���μ����ش� �������� �ʴ°�?����� ������ ���� �ִ�.

�Ϲ������� ������ ���ɼ��� ����. ���� �Ҽ���� �����Ͽ� Ʋ���� ���� ���� �̷��� ���ڸ� ����Ҽ���� �Ѵ�. �̿� ���� ���μ����ذ� ������ ���ڸ� �ռ������ �θ���.

���⼭ �ڸ��� 100������ ���ڸ� ������ �����Ͽ� ���� �Ҽ����� �����Ͽ� ����. ����, ���� �Ҽ��� �ƴ϶�� �ٷ� ������ ���� ���������� �����Ѵ�. ��ǻ�͸� ����ϸ� �� ������ ���ڸ� �ϼ����� ������ �� �ִ�. �̿� ���� �Ͽ� �ɷ��� ���� �Ҽ� �� ���� �����Ѵ�.

���� �� �ΰ��� ���ڴ� �Ҽ��� Ȯ���� ���� ��, �Ҽ���� Ȯ���� �����Ƿ� �ΰ��� ���ڴ� �� ���� �Ҽ� �������� �̿��Ͽ� �ݺ� ������ ���� ������ �ȴ�.

�Ϲ������� Adleman-Rumely��� �Ҽ� �������� ����ϸ� 100%�� Ȯ����(�Ǵ� Ȯ���ϰ�) ������ �����ϴ�. ����, �� ����� ��꿡 �ణ �ð��� �ɸ��Ƿ� ���� �Ҽ� ������ Ȯ�������� ���Ҽ��� Ȯ���� 99.9999999%���� ���ڸ� �߰��� ��쿡�� �� ����� ����Ͽ� ���� �����ϴµ� ����� �� �ִ�.

���Ǹ� ��← ������ �ڸ��� 100 ������ �� ���� �Ҽ��� ���ϸ�, �ڸ��� 200������ �ռ���(�� �Ҽ��� �ƴ� ��)�� �ȴ�. �տ��� ������ ��ó��, �Ҽ����� �ƴ��� �����ϴ� ���� ���� �����ϹǷ� �ڸ��� 200 ������ ���ڵ� �Ҽ����� �ƴ��� ������ �ϸ�, ���Ҽ��� �ƴϴ١���� ������ ������ ���̴�.

���Ҽ��� �ƴϴ١���� ������ ������, ���μ����ذ� �����ϰ�����, �ڸ��� 200������ ���ڴ� 10��� ���� �ҿ�ǹǷ� ���� �����ϴٰ� �� �� �ִ�.

5. Ÿ������� MPQS��

        ���μ� ������ ������� �����Ͽ�����, ���� ���μ� ������ ��ȿ�� ������μ� Ÿ�����(ECM, Elliptic Curve Method)�� MPQS(Multiple Polynomial Quadratic Sieve) �� ������ ���� �� �� �ִ�. �ֱ� ���μ� ���ص� ������ �϶�ǥ�� Ȯ���ϸ� ��κ��� Ÿ������� �ƴϸ� MPQS��� �˷��� �ִ�.

Ÿ�� ����� �μ����ظ� �����Ϸ��� ������ ����(��� ���μ��� ������ �ִ°�)�� ���� �μ����ؿ� �ɸ��� �ð��� �����ȴ�. �ڸ����� ����������, �� ���� ������ ���� �ܽð��� �μ����ذ� ����������.

����, MPQS���� �μ����� �Ϸ��� �ϴ� ������ ������ �¿���� �ʰ�, �ڸ������� �����Ѵ�. �ֱٿ��� NFS(Number Field Sieve)��� ���μ����ع��� ���ǰ� �ִ�.

�̵� ����� ����ϴ���, 60 �ڸ����� ���μ����ؿ� 15-30��, 80 �ڸ������� 40�ð� ���� (Pentium 200MHz ����), 100 �ڸ������� 0.5-1�� ���� �ҿ�ȴٰ� �Ѵ�.

���� RSA ��ȣ�� ���Ǵ� 200�ڸ��� ������ ������ ���μ����ش� �� 10��� ���� �ð��� �ɸ��ٰ� ����, ���μ������� ������� ��ȣ�� ������ �ȴٴ� ���� ������ �� �ִ�.

6. ������ũ����

        ���μ� ���� �̿ܿ��� ���Ϲ����ࡱ �Լ��� �����Ѵ�. ������ ���迡�� "������ũ�� ����"�� �˷��� ���� �װ��̴�. ���� ���,

   1, 3, 4, 5, 13, 14, 17, 18, 23, 29

��� ���ڰ� �ִٰ� ��������. �̵� ���ڸ� �����ؼ�(������� �ʴ� ���ڰ� �־ ����),

"���� ���Ͽ� ������ 50�� �Ǵ� ������ �����ϴ°�?", "�����Ѵٸ� �׿� ���� ������ ���� �󸶳� �����ϴ°�?"��� �����̴�.

�� ������ ���ڰ� �־���� 10�� ���� �����Ƿ�, �ڼ��� �����ϸ� �ᱹ�� �ش��� �����ϴ���, �� ���� ������ �����ϴ��� �� �� ���� ���̴�. �Ϲ������� �� ������ ���ؼ� ���̰��̴١���� �������� �ع��� ������, ������ ���� �󸶳� �ִ����� �������� ������ �� �ȴ�.

�׷��Ƿ� ���ڰ� 100��, 1000����� ������ �þ���� �ð��� ���� �ɸ��� �ȴ�.

�̷��� ������ ���п��� "P = NP����"��� ������ ������ ���谡 �ִ�. ������ ��� ���� ������ ���÷� ����.

 �� �ش�

숫자 알파벳 암호 - susja alpabes amho

�̿� ���� �Ϲ����� �ع��� �����Ѵٸ�, �̸� ��꿡 �ʿ��� �ð��� �뷫 �ľ��� �� �ִ�. �̰��� �����׽� �ð�(Polynomial-time)���� Ǯ�� �Ѵ١���� ���Ѵ�.

�̿� ���Ͽ� ���μ����� �� ������ũ�� ������ �������� �ع��� �˷��� ���� �����Ƿ� ������ �� �ִ� ��츦 �����س��� ���ۿ� ����. �̷��� ������ "���׽� �ð����δ� Ǯ �� ����(Non -deterministic Polynomial-time)"�̶� �Ѵ�.

�׷��� ���μ����� �� ������ũ ������ Ǯ�� ���� ������ ������� ����, ���� ����� �߰��� ���� �ִ�.

���⼭ P������ NP������ ���ؼ�,

(1)(�� ���󿡴� �Ϲ����� �ع��� �ִ� ������ ������ �����Ͽ� ������ �� �ִ� ���� �� ������ �з��� �� �ִ�)

(2)(�����غ��� ��� ������ �Ϲ����� �ع��� ����)

�� ��� �ʿ� �ش��ϴ� �������� �ǹ��� �����. �����ڸ� �����Ͽ� �Ӹ��� �پ ����̶�� ���� ������ �ع��� �߰ߵ��� �ʾ��� ���̹Ƿ���� ������ �� ������, ���� �̸� ������ ����� �ƹ��� ����.

7. ������ ����

�� modulus

� ���� ���� �ڿ� ������ ���ڿ� �ָ��� ����. ���� ��� 57�� 13���� ������

 

숫자 알파벳 암호 - susja alpabes amho

�� �ǹǷ�, 13�� �������� ���� ��� 57�� 5�� ������ ���ڷ� ������ �� �ִ�. �̸�

�� ���� ���� �� �ִ�. �ٸ� ���� ���,

�� ����

������ ���, 3�� 1/3�� ���ϸ� 1�� �ȴ�. �̿� ���� ��� ���ڿ� ������ �Ͽ� 1�� �ǵ��� �ϴ� ���ڸ� �����̶�� �θ���(������ ���� ������� �θ��� ���� ������ ���̴�). 13�� ��������, 5�� ������ ���Ͽ� ����.

���� ����, 5�� ������ 8�� �ȴ�.

�� �ݺ� ������

�� ������� ���� ����� ȿ�������� �� �� �ִ�. �ִ� �״�� ����Ѵٸ� 9ȸ ������ �����Ͽ��� ������, ������ ���� �ϸ� ������ Ƚ���� �پ��� ���� �� �� �ִ�.

숫자 알파벳 암호 - susja alpabes amho

��ǻ�͸� �̿��� ���, �� ���� ������ �����Ͽ��°��� ������ �ǹǷ�

7 X 7, 49 X 49, 2401 X 2401, 5764801 X 49

�����ؼ� 4���� �������� ����� �����ϴ�. ������������ ��꿡 ���ؼ��� 9���� ���������� �����ϹǷ�, �� ����� �̿��ϸ� ����� ������ ������ �� �ִ�(Ȯ���� ����).

�� �ִ�����

a, b�� �ִ������� gcd(a,b)��� �Ǵ� �ܼ��� (a,b)��� ����ϱ�� ����(gcd�� greatest common divisor). Ư�� (a,b) = 1�� �� ���, a�� b�� ���μ���� �Ѵ�. ���� ���,

        (10,6) = 2

        (24,15) = 3

        (24,36) = 12

        (7,6)  = 1.

�� ���Ϸ� �Լ�

���Ϸ� �Լ��̶�� ������ �����ϴ� ���� a�� (a,n)=1�� �Ǵ� ������ ������ �ǹ��Ѵ�.

���� ���,�̶�� ������ �����ϴ� ����(a=1,2,3,4,5,6,7,8,9)�߿��� (a,10)=1�� �Ǵ� ����(�ᱹ ���μҰ� �Ǵ� ����)�� ������ �ǹ��ϹǷ�

        (1,10) = 1

        (2,10) = 2

        (3, 10) = 1

        (4, 10) = 2

        (5, 10) = 5

        (6,10) = 2

        (7,10) = 1

        (8,10) = 2

        (9,10) = 1

�� �ǹǷ�, a=1,3,7,9�� 4���� �Ǿ�=4�� �ȴ�. ���� ���Ϸ� �Լ��� ������ ������ �����Ѵ�.

�� ���Ϸ� �Լ��� ����(1)

p�� �Ҽ����,�� �ȴ�.

���� ��� 13�� �Ҽ��̹Ƿ�,�� �ȴ�. �ֳ��ϸ��̶�� ���������� ���� �߿��� (a,13)=1�� �Ǵ� ������ ������ �ǹ��Ѵ�. ���� ���μҰ� ���� �ʴ� ���� �߰��Ѵٸ� ����� �����Ѵٴ� ���� �ǹ��ϹǷ� 13�� �Ҽ���� ������ ���ݵȴ�. �׷��Ƿ� p�� �Ҽ��� ���� ���Ϸ� �Լ��� ����� �ſ� �����ϴ�(�ռ����� ���� ���� ������ �ʿ��ϴ�).

�� ���Ϸ� �Լ��� ����(2)

n = ab, (a,b)=1�̸�,�� �ȴ�.

���� ���, 91 = 7 X 13, (7,13) = 1�̹Ƿ�,

��� ���ȴ�.

���������� 84 = 7 X 12, (7,12)=1�̹Ƿ�,������ ��������,�� 12�� �Ҽ��� �ƴϹǷ� ������ ������ �ʴ´�.

�� �丣���� ����

p�� �Ҽ���� �����ϸ�, (a,p)=1�� �ǵ��� �ϴ� a�� ���ؼ���

�� �����Ѵ�.

���μ� 13�� �Ҽ��̹Ƿ�, (a,13)=1�� �Ǵ� ��� a�� ���ؼ���

�� �ȴ�. ��ü������

 �� �ȴ�. ������ �����

숫자 알파벳 암호 - susja alpabes amho

�� ���� �ݺ� �������� 13�� �̿��� ������ ������ ���Ͽ� ����� ���������ν� Ŀ�ٶ� ���ڸ� ������� �ʰ��� ȿ�������� ����� �����ϴ�.

�� ���Ϸ��� ����

m�� ���� ����(�ݵ�� �Ҽ��� �ʿ�� ����)��� ����.

�̶� (a,m)=1�� �����ϸ��� �����Ѵ�.

���μ� m=15��� �ϸ�

�� �ǹǷ� (a,m)=1�̸��� �����ȴٰ� �ٲپ� ���� �� �ִ�. ���⼭ a=1,��,14�߿���, 15�� ���μ��� ���� ã����

(1,15) = 1

(2,15) = 1

(3,15) = 3

(4,15) = 1

(5,15) = 5

(6,15) = 3

(7,15) = 1

(8,15) = 1

(9,15) = 3

(10,15) = 5

(11,15) = 1

(12,15) = 3

(13,15) = 1

(14,15) = 1

�� �ǹǷ�, a=1,2,4,7,8,11,13,14�� �ȴ�. ���� ����Ͽ� ����

�� �ǹǷ�, ������ �Ǵٴ� ���� Ȯ���� �� �ִ�.

�� ������Ģ(1) :�� �����Ѵ�.

���� ���,

숫자 알파벳 암호 - susja alpabes amho

�� ������Ģ(2) :

숫자 알파벳 암호 - susja alpabes amho

8. �޽����� ��ġȭ

        �޽����� ��ġȭ���� ��Ÿ�� ����. ����� ���� ���� ���� �� ������, ���⿡���� 26���� ǥ�ø� ����ϴ� ������ �Ѵ�. ���, 267�� 10������ �ǹ��Ѵ�. 10������ ��Ȯ�� �ϱ� ���ؼ��� (267)10�̶�� ǥ���ϸ� �ȴ�. �̰���

2X+ 6X+ 7X= 2X100 + 6X10 + 7X1 = 267�̶�� �ǹ̴�.

���������� 2���� ǥ���� 1101�� (1101)2��� ����, 10������ �ٽ� ǥ���ϸ�

1X+ 1X+ 0X+ 1X= 1X8 + 1X4 + 0X2 + 1X1 = 13

�� �ȴ�. ���ĺ��� ���� 26���ڷ� ���ĺ��� ��ġ�� ȯ���ϸ�, 26���� ǥ�ð� �����ϴ�. ���� ���, a=0, b=1, c=2, ��, z=25��� ��������. cat�̶�� ���ڿ��� ���ڷ� �ٲٸ� 2, 0, 19�� �ȴ�. �̰��� 26������ ǥ���ϱ� ����, 10������ �ٲٸ�

2X+ 0X+ 19X= 2X676 + 0X26 + 19X1 = 1352 + 0 + 19 = 1371

�� �ȴ�. ���� cat�̶�� ���ڿ��� 1371�̶�� ���ڸ� ������ �Ͱ� ����. ������ 1371�̶�� ���ڸ� 26������ ǥ���ϸ� 2, 0, 19��� ������ ������Ƿ� cat�̶�� ���ڿ��� �ٲٴ� ���� �����ϴ�. cat�̶�� ���ڿ��� 1371�̶�� ���ڿ� 1��1 ������ ���״ٴ� ���� ��������.

���⼭ ���޽����� ������ ����, ���ڸ� ������ �Ͱ� ���١���� �����ϸ�, �����δ� �����ڸ� �̿��� ��쿡�� ���?�� �Ǵ� �������� ��� ǥ���ϴ°�?����� ����� ������ ������, ������ ������ ���������� �����ϱ� �ٶ���.

9. RSA ��� ��

        ���� ��ȣȭ�� �����Ͽ� ����.

1371(cat�̶�� ���ڿ��� ��ġȭ��Ų ���� �������)�� ��ȣȭ�ϸ�, ������ �̿��Ͽ� 1371���� ū �� ���� �Ҽ��� ������ ������ �� �ִ�. ���⼭�� 43�� 53���� ��������(43X53=2279). �׸��� 43�� 53�̶�� ���ڴ� ��п� ���̰�, 2279��� ���ڴ� �����ϴ� ������ �Ѵ�(�̰��� ����Ű�� �ϳ��� �ȴ�). ���������� ����Ѵ�. �� ��쿡

- 2279 = 43 X 53

- 43�� 53�� �Ҽ��̴�.

- 43�� 53�� ���μ�

��� ��Ƿκ���, ���Ϸ� �Լ��� ���� (1), (2)�� ����ϸ� ������ ���� �� �ִ�. �ᱹ ������ ���� �ȴ�.

숫자 알파벳 암호 - susja alpabes amho

��������, �� 2184�� ���μҰ� �Ǵ� ���ڸ� ������ ������ ������. ���⼭�� 1241�� ��������(�̰͵� ����Ű�� �ȴ�).

�������� 2184�� 1241�� ������ ���ϸ� 1649�� �ȴ�(�̰͵� ����Ű�̴�). Ȯ���Ͽ� ����,

1249 X 1649 = 2046409            (1)

            = 1 ( mod 2184)       (2)

�� �ǹǷ�, 1649�� 1241�� ������ �ȴٴ� ���� Ȯ���� �� �ִ�. ���� ������ ����

2046409 / 2184 = 937��1

�� �ȴ�. �̰���

2046409 = 2184 X 937 + 1           (3)

�� �Ͱ� ����.

�ټ� ���ڰ� ������������, �����Ͽ� ���� ������ ����.

- ������ 2279�� 1241

- ����� 1649

- 43�� 53�� 2184�� ���

������ ���ϸ�, �������� �޽����� ���� ���, 1241�� ���ϰ�, 2279�� ������ ����(�����ڸ� 2279�� ���� ������)�� �������䡱��� ���� �ȴ�.

1371(cat�̶�� ���ڿ��� ��ġȭ��Ų ��)�� ����Ű 1241�� 2279�� ����Ͽ� ��ȣȭ�ϸ�

1371^(1241) = 2003 (mod 2279)            (4)

�� ���� �ȴ�. ���⼭ 2003�̶�� ���ڰ� ��ȣ���� �ȴ�.

��ȣȭ�ϱ� ���� ���Ű 1649�� �̿��ϸ�,

2003^(1649) = [(1371^(1241)]^(1649) (mod 2279)        (5)

            = 1371^(1241 X 1649) (mod 2279)           (6)

            = 1371^(2046409) (mod 2279                (7)

            = 1371^(2184 X 937 + 1) (mod 2279)       (8)

            = 1371^(2184 X 937) X 1371^(1) (mod 2279) (9)

            = [1371^(2184)]^(937) X 1371 (mod 2279)  (10)

            = 1^(1371) (mod 2279)                      (11)

            = 1 X 1371 (mod 2279)                     (12)

            = 1371 (mod 2279)                         (13)

�� ���� �ǹǷ�, ������� �����ϴ� ���� �����ϰ� �ȴ�.

[����]

(5)�� ��ȯ�� (4)�� �̿�

(5)->(6) ������Ģ(2) ���

(6)->(7) (1)�� ���

(7)->(8) (3)�� ���

(8) -> (9) ������Ģ (1) ���

(9)->(10) ������Ģ (2) ���

(10)->(11) 1371�� 2279�� ���μ��̹Ƿ�, ���Ϸ� �����κ���

1371^() = 1 (mod 2279)

�� ���� �ȴ�. �� ���� �����ϸ�

1371^2184 = 1 (mod 2279)         (14)

�� �ȴ�.

[�ּ�]

(11)->(12) 1�� �� ���� ���ص� 1�̴�.

(12)->(13) ������ �˰� �ִ�.

����� �ִٸ� (2)�İ� (14)���� ����Ͽ�, (6)->(12)������ �dzʶ� ���� ������ ���̴�.

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

�� �������� ����Ű�� 2279, 1241 �� ���� ���ڸ� ����Ͽ�����, ����Ű�� �ѹ� �����ϸ� ���� �����ϴ� ���� ��ƴ�(�޽����� �����ϴ� �ʿ����� ���������).

�׷��Ƿ� �޽����� ���� ����Ű�� ������ ���� �λ��� �� �� ������, �����δ� ���� ����Ű�� ������ �� �̿� ���Ͽ� �޽����� �����Ѵ�.

������ ����Ű�� �ڸ��� 200������ ���ڰ� �ǹǷ�, �� ������ �������� �޽����� ������ ������ ���� ������ �ʿ��ϴ�. ���� ���, �޽����� �� ��쿡�� 20���� ������ �����Ͽ�, ���� �� �۽��ϸ� �ȴ�.

�� RSA�� �������°�?

�� ��ȣ�� ���� ����, ���Ű 1649�� ȹ���� �ʿ䰡 ������, 1649�� 2184�� ������ 1241�� �����̴�. 1241�� �����Ǿ� �����Ƿ� ������ ���� ������, 2184�� ����̹Ƿ� �ص��ϱ� ���ؼ��� 2279������ ������� ������ �� �ȴ�.

�츮�� 2279 = 43 X 53�̶�� ����� �˰� �����Ƿ�, ���Ϸ� �Լ��� ���� (1), (2)�� ��������ν� ������ ����Ͽ�����, �̸� �𸣴� ����� 2279�� ���μ����� �� �ʿ䰡 �ִ�.

�׷��� �����δ� �ڸ��� 200 ������ ���ڰ� ���ǹǷ� ���μ����ش� ���� �Ұ����ϴٰ� �� �� �ִ�. ���쿬�� ������ ���ڷ� ����� ���μ����ذ� �Ǿ��١��� ���ɼ��� ���� ����ϴٰ� �� �� �ִ�.

10. RSA ����Ű ��ȣ

        RSA ����Ű ��ȣ�� �� ��ȣ�� ������ Rivest, Shamir, Adleman 3���� �̸� ���ڸ� ���� ���̰� �Ǿ���. �� ��ȣ�� �ٰ��� �̷�� ���� ���μ����ذ� ����� ��ƴٴ� ����̴�. ���������� �� �������� ���ؼ��� �߰��� ��ť��Ƽ�� �ڶ��ϰ� ������, ��꿡 �ð��� ���� �ҿ�ȴٴ� ������ ������ �ִ�.

RSA�� DES�� ���Ͽ� ����Ʈ�������� ���鿡�� ����� ��, �ϵ���� ���鿡���� õ���� �Ͽ��� �ϸ����� �� ���� �ӵ��� ���´ٰ� �Ѵ�. ���� ����Ű ��ȣ����� �ϳ��� RSA�� ������ ���Ű ��ȣ��� DES���� ������ �̿��ϴ� ���� ȿ�����̶� �� �� �ִ�.

����� ��ȣ�� ���ؼ��� DES�� ����ϰ�(RSA�� ����ϴ� �ͺ��� �ð� ������ �ȴ�), ���������� ���ϴ� Ű ��ȯ���δ� RSA�� ����ϴ� ���� �������̶� �� �� �ִ�. ��� ��ȣ�� �Ͽ��� ���� Ű�� ��������� ����ϴ� ���� �����ϴ�. ���⼭ Ư�� DES�� ���� ������ ��ȣ�� ������ �������� Ű�� ��ȯ�ϴ� �۾��� �����Ѵ�.

���۵� Ű�� �ص��� �Ǹ�, ���� �������� �޽��� ��δ� �ص��ǰ� ����. ���� Ű�� �����ϴ� ���� �߿��� ��ſ��� �ټ� �ð��� �ɷ��� �����Ƿ�, �������� ���� RSA�� ����ϰ� �ȴ�. ���� ���, ����ũ�� ����Ʈ���� �����ͺ��̽� Access, ������ �������� Netscape Navigator ���� ���� ����Ʈ��� �̷��� RSA ����Ű�� �����ϰ� �ִ�.

11. ��ȣ �� PGP

        PGP(Pretty Good Privacy)�� 1991�� Zimmermann���� ���� ���������. �׷��� �������� �̱����� ��ȣ ���⿡ ���� ������ �־����Ƿ� �̱� ���ܿ��� ����ϴ� ���� �Ұ����ߴ�. �̷��� ������ PGP�� �⺻���� Schmacher�� ���� ������ PGP(PGPi)�� ����� �ƴ�. ���� �̱� �������� PGP��, �̱� �ܿ����� PGPi(PGP International)�� ���ǰ� �Ǿ���. 2000�� �ʹݿ� �̱������� ������ Ǯ���鼭 ���� 6.5.1i�� ���ķ� PGP ���� ������ ������� �Ǿ���. ���� 5���ʹ� GUI�� �����Ǹ� ���� ������ ����� �� �ִ�.

���� ����Ʈ:

ftp://pgp.iijlab.net/pub/pgp5/6.5/6.5.1int/PGPfreeware651int.exe

RSA ���� ��ȣ �ؼ��κп��� ������ �ٿ� ����, ���� �������� ������� PGP������ ��Ź��� ��ȣȭ�� ���� IDEA(International Data Encryption Algorithm)��� ������ ��ȣ �ý����� �̿��Ͽ� Ű�� ��ȣȭ�� ���� RSA�� ����ϰ� �ִ�.

12. DES ��ȣ

        DES��ȣ�� 1977��, �̱� �󹫼� ǥ�ر�(ANSI)���� ������ ��ȣȭ �԰�(Data Encryption Standard)�� ���� ���� �� IBM�� ������ ��Ŀ� ������ ������ ���̴�. �⺻������ DES�� ������ ��ȣ�迭������, ���� ���� ��ȣȭ ����� ������ ���Ͽ�, �ص��� ��Ƶ��� ���ȵǾ���. ��ǥ��ô� �ϵ��� �ʿ�� �Ͽ�����, ���߿��� ����Ʈ������ε� ������ �� �ְ� �Ǿ� UNIX ����� ���� �Ϲ������� ���̴� ��ȣ ����̴�.

�׷��� ��ȣȭ �԰��� �����̶�� ���鿡�� ����� �߿�õǾ����Ƿ�, �̱� �ٱ����� ����Ǵ� ���� ���� ����̾���(Netscape Navigator ��� ���Ǵ� RSA ������ȣ�� ���� ������� �ᱹ ������ ���ܿ� �� ������ �����Ͽ���. ���� ����� ���� ���Ǵ� Ű�� ��Ʈ���� ������).

���� DES�� ����� �����Ǿ� �����Ƿ� ����Ʈ������� ���������ϴ�. ���� ��ȣ���ڿ� ���ؼ� �����Ǿ����� �ص��� ���� ���ٰ� �Ѵ�. DES ��ǥ ��ô� �̱� ������ �㰡�� ���� ����� �ϵ����� DES�� �����������Ƿ� ��ȣ�� �������� ���ؼ� �ܺηκ����� �򰡴� ���� �̷������ ���Ͽ���.

��ȣȭ �˰������� �������� ���δ� Ŀ�ٶ� �����̴�. �˰������� �����ϸ�, ��ȣ�� �������� �ܺηκ��� �������� �򰡸� ���� �� �ִ�. �׷��� �ǿ��Ͽ� ������ ���ɼ��� ���� �ʴ�.

�˰������� �������� ������ �ǿ�ǰų� ���ݿ� ���� ������ �پ������, ��ȣ�� �������� ���� �������� �򰡸� �ޱ�� ����� ���̴�. ���� �ǵ������� �����Ͽ� ��ȣȭ �˰������� ������ ����� �ڽŸ��� �ص��� �� �ֵ��� �غ��Ͽ� �� ���� ���� ���̴�.

���γ� ������ �������� ���ȴٸ� �����������, ������� ���̱� ���ؼ��� �˰����� ������� Ŀ�ٶ� ��� ������ �ƴ� �� ����.

DES ��ȣ�� Ű�� ���̰� �����Ǿ� �ִ�. ������ DES ��ȣ�� 56bit Ű�� ����ϰ� �ִ�. �׸��� DES������ 56��Ʈ Ű�� ����ϴ� �ý��۰� 40��Ʈ�� ����ϴ� �ý��۰��� ȣȯ���� ���� ����, �ᱹ 40��Ʈ�� �ý��ۿ��� ���Ǵ� Ű�� 56��Ʈ �ý��ۿ����� ����� �� ����. ����, RSA ��ȣ �� PGP ��ȣ������ Ű�� ���̴� ����������� �����Ӱ� �ٲ� �� �ִ�(���� �ý��� ������ Ű�� bit���� ������ �� �ִ�). ���� Ŀ�ٶ� bit���� Ű�� ����� ���� ������, ���ð��� ���� �ҿ�ǹǷ� ������ Ʈ���̵������ �ʿ��ϴ�.

13. NSA(National Security Agency)

        ��ȣ�� �ŷ��ϴµ� NSA�� �������� ���� ���� ���̴�. NSA�� �̱� �����������屹�� �ǹ��ϸ�, �� �ӹ��� �̱� ������ ��Ű�� ���� ���� ��κ��� ����� ��û, ��û�Ѵ�. �̸� ���ؼ� NSA�� �� ������ �̱� ������ ������ �ִ� �������̶�� ��Ʈ��ũ�� ����Ͽ� ��� ����� �����ϰ� �ִ�. ���� ���̺����� ��û�Ⱑ ��ġ�Ǿ� �ִٰ� �� �����̴�.

Ȱ���� �����װ� ���߻���� �߻����� ����, ��ũ������ ������ �ҷ� ������� ���� ������ ���ų����� ��û�Ͽ� �̱� ���� �����ɷ��� �ڶ��Ͽ���. 1996�⿡ �߻��� ��� �Ϻ� ������ ���� ���Ż�ǿ����� ������ Ư���δ� ������ �̸� �˾�ë�ٰ� �ϴ� �̰͵� NSA�� �ɷ��̴�.

NSA�� ���� �˰� ������ http://www.nsa.org/�� �湮�ϸ� �ȴ�. ��ȣ�ڹ����� �� ���� �� ���� ���̴�. ���� 2���������� ���ϰ� �Ϻ��� ����� ������ ��ȣ�� ���ϱ׸��� ���õǾ� �ִ�. ����� �ص����� ���� ���̶�� �Ͼ��� ���ϱ׸���, ���� ���ձ������� �ص��ϰ� �־����� ������ ������ ���� �־��ٴ� ����� �̹� �˰� ���� ���̴�. ���ָ� ���ݿ� ���ؼ��� ������ �˰� �����鼭�� ��ȣ�� �ص��ϰ� �־��ٴ� ����� �𸣰� �־�, ������ �ް� �Ǿ��ٰ� �Ѵ�.

NSA������ �ӹ� ������� ������ ��ȣ����� �̷������ ���� ŽŹġ �ʰ� ����� �ִ�. �̷��� �� ���, NSA�� �ӹ� ������ ������ �̷������ �ʰ� �DZ� �����̴�. NSA������ ������ ����� ���� ���� ��ǻ��, ������ ������, ����ڸ� �ʿ�� �ϰ� ������, ������ RSA ��ȣ�� ���� ���� �Ұ����ϴ�(���� ������ �㰡�� 56��Ʈ DES ������ NSA ���� ��ǻ�͸� ������ ������ �ص� �����ϴٰ� �Ѵ�). �̷��� ������ �̱� ���δ� ��ȣ�� ���⿡ ���ؼ� ������ ������ �ϰ� �ִ�. �̱� ����� �پ ��ȣȭ ����� ������ �������� �ұ��ϰ� �̱� ������ ����� �����Ӱ� �ŷ��� �� �� ����.

��Ե� ��ȣȭ ����� �����Ϸ��� �̱� ����������, �̿� �ݴ��ϴ� ������ ����� ���׿� �ֱ�(1997���)���� ������ �ణ ��ȭ�Ͽ� ������ Ű�� �̱� ���ο� �����ϸ�, ���ܷ� ��ȣ����� �����Ӱ� �����ϴ� ���� �����Ѵٴ� ��ħ�� �����Ҵ�(��ǻ� �����ϰ� �ִٴ� ������ ������ ����).  ���Ǻ��� ����� �Ǵܿ� ������, �̱� ���δ� ������ Ű�� �̿��Ͽ� ��ȣ����� �ص��ϴ� ���� �����ϴٰ� �Ѵ�(������ �ſ��� �� �ִ°�?).

14. �� ��

�� Camellia: NTT�� �����ð� ������ ���Ͼ�ȣ�̴�. AES�� ������ ��ȣ������� E2�� ������ �� ������ �򰡱���� ���� ������� ���̴�.

�� MultiPrime: ��ȣȭ ��Ŷ RSA BSAFE WTLS-C�� ä��� ��ȣ����̴�. RSA �˰������� ����Ѵ�. ��� RSA �˰����򿡼��� �ΰ��� �Ҽ��� ����ϰ� ������, MultiPrime������ 3���� �Ҽ��� ����Ѵ�. ������ RSA ����Ű ��ȣ����� �̿��� ��Ŵ ������ ���� �������� �ʵ��� RSA �˰������� ���ȿ���� ����ų �� �ִ� �پ ����� �˷��� �ִ�.

�� Blowfish: Web�󿡼� ��ȣȭ�� ������ ����Ʈ���� ���Ǵ� �˰������̴�. �̷��� �ؼ�, ��ȣ�� ���� ������ ���ϰ� �ִ�. http://www.encryption.com/

�� CAST: PGP 5.X���� ä��� ���Ű�̴�. Northern Telecom���� Carlisle Adams�� Stafford Tavares�� ���� ���������.

�� MALTI2, MALTI4, M6: ����ġ���� ���ȵ� ��ȣ�̴�. ���� ���� �����й�ۿ� ���ǰ� �ִ�.

�� Ÿ�����ȣ: ������Ÿ���⿡�� ������ ��ȣ�̴�.

�� MISTY: ���������⿡�� ������ ��ȣ�̴�. ����Ű ��ȣ�� �ϳ��� ���а��ݿ� ���ϴٰ� �˷����ִ�.

�� FEAL(Fast Data Encipherment ALgorithm): NTT�� ������ ������ ��ȣ�̴�.

��ȣȭ�� �������� ����������, �ᱹ �ص��� �����ϴٴ� ���� �˷��� ���� ������ �̷������. �׷��� �׶����� �ص��ǰ� ����, �� ��ȣ�� ���� �򰡴� ���� ������ �ִ�.

�� RC2, RC4, RC5, RC6(Rivest Cipher �Ǵ� Ron's Code 2,4,5,6):

RSA���� Ron Rivest�� ������ ���� ����� ��ȣ(���Ű ��ȣ)�̴�. Netscape Navigator���� ���ǰ� �ִ�. �˰������� ������� �Ǿ� �ִ�.

�� Skipjack: NSA(National Security Agency)�� ������ Clipper Ĩ�̶�� ��ȣȭ Ĩ�� ����� ��ȣȭ �˰������̴�. ���� ���� �˰������� ������� �Ǿ� �־�����, �ٷ��� �����Ǿ���. ��ȣ���ڿ� ���� �ص��Ǿ�, ����� ������ ��ȣ?

�� MD2, MD4, MD5: RSA���� Rivest�� ������ �޽��� ��������Ʈ �Լ��̴�. ��� ������ ���� ���� ���� ������ ���ڿ��μ� ����Ѵ�. PGP ��ȣ�� ����Ű ����(Key fingerprint)�̶�� ���� ����Ű�� MD5�� ����� ��� �װ��̴�.