R 中的 RSA 实现示例
Example RSA implementation in R
这确实超出了我的理解范围，但我实在是太好奇了，不得不试一试。
Edward Frenkel 写了这篇非常简单的文章 article in slate。他用非常简单的术语解释了 RSA 的工作原理并给出了示例。我想在 R 中尝试这个，看看我是否可以复制它。
我从他的素数 3 和 5 的例子开始。"Then (p – 1)(q – 1) + 1 = (3 – 1)(5 – 1) + 1 = 9"。 9 可以拆分成 3 * 3。所以
p = 3
q = 5
N = 15
r = 3
s = 3
到目前为止一切顺利，只是它不起作用。我的猜测是，这是因为 N 是 3 的因数，所以这又回到了费马最初的小定理。
好的，所以 RSA 方程的结果需要是：1) 不是质数，2) 可分解为两个不是 N 因数的数字。事实证明，这方面的例子并不多，我现在明白为什么 Frenkel 没有在文章的这一部分用另一个例子来阐述了！
我终于确定了
p = 31
q = 37
N = 1147
r = 23
s = 47
当然这些数字对于R的int来说太大了，所以我使用了gmp包。现在，如果我拿一个样本编号进行解码，比如说 24，我就会得到这个。
library(gmp)
as.bigz(24^r) %% N
# Big Integer ('bigz') :
# [1] 331
as.bigz(331^s) %% N
# Big Integer ('bigz') :
# [1] 465
这又回到了我能达到的数学水平，即 465 不等于 24。
我哪里出错了？
我不知道您的实施情况，但您在使用 bigz 时犯了一个常见错误。 as.bigz(x^y) 仅作用于值 x^y 的 "base" 实现。您需要编写 x^(bigz(y)) 以将实际计算强制转换为大整数 class。考虑：
> foo <- as.bigz(23^875)
> bar <- 23^(as.bigz(875))
> foo-bar
Big Integer ('bigz') :
[1] 173766203193809456599982445949435627061939786100117250547173286503262376022458008465094333630120854338003194362163007597987225472483598640843335685441710193966274131338557192586399006789292714554767500194796127964596906605976605873665859580600161998556511368530960400907199253450604168622770350228527124626728538626805418833470107651091641919900725415994689920112219170907023561354484047025713734651608777544579846111001059482132180956689444108315785401642188044178788629853592228467331730519810763559577944882016286493908631503101121166109571682295769470379514531105239965209245314082665518579335511291525230373316486697786532335206274149240813489201828773854353041855598709390675430960381072270432383913542702130202430186637321862331068861776780211082856984506050024895394320139435868484643843368002496089956046419964019877586845530207748994394501505588146979082629871366088121763790555364513243984244004147636040219136443410377798011608722717131323621700159335786445601947601694025107888293017058178562647175461026384343438874861406516767158373279032321096262126551620255666605185789463207944391905756886829667520553014724372245300878786091700563444079107099009003380230356461989260377273986023281444076082783406821221904389928892660558992836584689744476863579307237496414568003846808286835850208746181481557645824713444905818642923064268658195509625918466444650382085475088234562378101921214427179437742847283767434306518359957311828817552403374413253648610960585668783098363467119582330958796937261035413592452252131671852390671592802688749850788514826262090255205005577571366541443538143160704804527447401296583096054981769466917484102135185441507991470784562950910215560441960379597002170300547435187143508062255844395408792944293400831831795566646329416511193212832923226323120404081092400841930612946287554533690559338257386838001380803072132077309936022498050235973754946108111287350398641170739150864953041877814592188607283695369537692538586785411834112926217758723900966685098645453563475609351753530469557589057290519159806133678120681750553758265808719760526017648046327072778049156254469071817016393730845185472213535888596169326926919296583452231894742256653465765066432901458967285013809247464106996628890408157081411997684227122115338859158363030326291909119925357416316195562067909241887465686042001962647100968496756163689270274883225844011829128304727462911444081923209114398978559088569
# easier way to verify they're different:
> log10(foo)
[1] 2408.24
> log10(bar)
[1] 1191.512
这确实超出了我的理解范围，但我实在是太好奇了，不得不试一试。
Edward Frenkel 写了这篇非常简单的文章 article in slate。他用非常简单的术语解释了 RSA 的工作原理并给出了示例。我想在 R 中尝试这个，看看我是否可以复制它。
我从他的素数 3 和 5 的例子开始。"Then (p – 1)(q – 1) + 1 = (3 – 1)(5 – 1) + 1 = 9"。 9 可以拆分成 3 * 3。所以
p = 3
q = 5
N = 15
r = 3
s = 3
到目前为止一切顺利，只是它不起作用。我的猜测是，这是因为 N 是 3 的因数，所以这又回到了费马最初的小定理。
好的，所以 RSA 方程的结果需要是：1) 不是质数，2) 可分解为两个不是 N 因数的数字。事实证明，这方面的例子并不多，我现在明白为什么 Frenkel 没有在文章的这一部分用另一个例子来阐述了！
我终于确定了
p = 31
q = 37
N = 1147
r = 23
s = 47
当然这些数字对于R的int来说太大了，所以我使用了gmp包。现在，如果我拿一个样本编号进行解码，比如说 24，我就会得到这个。
library(gmp)
as.bigz(24^r) %% N
# Big Integer ('bigz') :
# [1] 331
as.bigz(331^s) %% N
# Big Integer ('bigz') :
# [1] 465
这又回到了我能达到的数学水平，即 465 不等于 24。
我哪里出错了？
我不知道您的实施情况，但您在使用 bigz 时犯了一个常见错误。 as.bigz(x^y) 仅作用于值 x^y 的 "base" 实现。您需要编写 x^(bigz(y)) 以将实际计算强制转换为大整数 class。考虑：
> foo <- as.bigz(23^875)
> bar <- 23^(as.bigz(875))
> foo-bar
Big Integer ('bigz') :
[1] 173766203193809456599982445949435627061939786100117250547173286503262376022458008465094333630120854338003194362163007597987225472483598640843335685441710193966274131338557192586399006789292714554767500194796127964596906605976605873665859580600161998556511368530960400907199253450604168622770350228527124626728538626805418833470107651091641919900725415994689920112219170907023561354484047025713734651608777544579846111001059482132180956689444108315785401642188044178788629853592228467331730519810763559577944882016286493908631503101121166109571682295769470379514531105239965209245314082665518579335511291525230373316486697786532335206274149240813489201828773854353041855598709390675430960381072270432383913542702130202430186637321862331068861776780211082856984506050024895394320139435868484643843368002496089956046419964019877586845530207748994394501505588146979082629871366088121763790555364513243984244004147636040219136443410377798011608722717131323621700159335786445601947601694025107888293017058178562647175461026384343438874861406516767158373279032321096262126551620255666605185789463207944391905756886829667520553014724372245300878786091700563444079107099009003380230356461989260377273986023281444076082783406821221904389928892660558992836584689744476863579307237496414568003846808286835850208746181481557645824713444905818642923064268658195509625918466444650382085475088234562378101921214427179437742847283767434306518359957311828817552403374413253648610960585668783098363467119582330958796937261035413592452252131671852390671592802688749850788514826262090255205005577571366541443538143160704804527447401296583096054981769466917484102135185441507991470784562950910215560441960379597002170300547435187143508062255844395408792944293400831831795566646329416511193212832923226323120404081092400841930612946287554533690559338257386838001380803072132077309936022498050235973754946108111287350398641170739150864953041877814592188607283695369537692538586785411834112926217758723900966685098645453563475609351753530469557589057290519159806133678120681750553758265808719760526017648046327072778049156254469071817016393730845185472213535888596169326926919296583452231894742256653465765066432901458967285013809247464106996628890408157081411997684227122115338859158363030326291909119925357416316195562067909241887465686042001962647100968496756163689270274883225844011829128304727462911444081923209114398978559088569
# easier way to verify they're different:
> log10(foo)
[1] 2408.24
> log10(bar)
[1] 1191.512