数学とコンピュータⅡ advent calendar 2017の記事です。連分数を用いてplain RSA暗号が攻撃できる(Wiener's attack)という定理の概要を説明します。また、Wiener's attackをR言語の関数として実装します。 目次 1.plain RSA暗号とは? 2.Wiener's attackとは? 3.攻撃の要:とても近い値を持つ2つの有理数 4.連分数近似:近い有理数をあぶりだす方法 5.試しにやってみよう 6.公開鍵だけで所望のk/dが得られたか判定する方法 7.Wiener's attackが可能な秘密鍵dの大きさ 8.R言語でWiener's attackの関数を実装しよう 1.plain RSA暗号とは?plain RSA暗号とは、公開鍵暗号の一種です。公開鍵暗号は他者に公開する公開鍵と他者には秘匿にする秘密鍵からなります。平文を送る側は公開