ここで、最大公約数を求めるために u1 と u2 に対して、ユークリッドの互除法を適用します。すると、q の値が求められます。実際に Python で実行すると、以下のようなコードとなります。
def gcd(x, y):
r = modlog(x, y)
while r != 0:
x = y
y = r
r = modlog(x, y)
return y
def modlog(x, y):
r = x % y
return r
def main():
u1 = 20912068408571562329765690555061159289641629285082404210189101064954330953315593257557260077525915152641073106397431556875680393639301995231540409600633056790407217644109479375811025952060540276714119842291972532268686811648476477127818267411283106601195166099848608860814911133056759210847640244371352294577674757844032344743192797680553522630615249481210459669536735468283778508143359159893770374788694416907786510825727199111604249000530550012491935109887922826382346971222271516625157446929215544796309806757863550058676780306722906895167581167203804721314732494889662194466565293268848629536070864750745494338531
u2 = 20810915617344661448636429656557804394262814688853534649734586652859523797380885650024809244693377123486154907319690068259378744245911427062593140588104970879344505836367952513105241451799550533959908906245319537215140226739848280012005678383612764589285444929414256249733809498630880134204967826503346173071037885178145189051140796573786694250069189599080301164473268293037575740360272856085402928759232391893060067823996007021668671352199570084430112300612196486186252109596457909476374557998336186613887204545677563178904634941310201398366965571422359228917354256271527331840144577394174480450746748283277750230727
q = gcd(u1, u2)
print(q)
if __name__=="__main__":
main()
RSAPrivateKey ::= SEQUENCE {
version Version,
modulus INTEGER, -- n
publicExponent INTEGER, -- e
privateExponent INTEGER, -- d
prime1 INTEGER, -- p
prime2 INTEGER, -- q
exponent1 INTEGER, -- d mod (p-1)
exponent2 INTEGER, -- d mod (q-1)
coefficient INTEGER, -- (inverse of q) mod p
otherPrimeInfos OtherPrimeInfos OPTIONAL
}
from Crypto.PublicKey import RSA
from Crypto.Util.number import inverse
p = 139446642537534304777628614240154046272434122794892522124374234093313897652592278876204620931659231555942782873768406065030569534203407105601097455479995730772421725109267044663491213232687718387909353507690622331780468229128999879032054673690005684809410661625656125511253714586807242182927209779610158700317
q = 149964660518396798660782215517197000054264985822608779681144262791391323000835825727277636178043097046988857828384650158626906824855399961360412435818827649355003329726451846544435103030378220357694459358803967598155925736581896165952170564324730092516286266118841005062382011803493961966912439338500328959743
e = 65537
n = p*q
d = inverse(e, (p-1)*(q-1))
key = RSA.construct(map(int, (n,e,d)))
print(key.exportKey().decode('utf-8'))
from Crypto.PublicKey import RSA
from Crypto.Util.number import inverse
p = 138772131683595539379264396620735603425702925342291987755841498194704959931781364169698055070785331880014332847610595576230231417278730047109315439655930883451174914691703480278864120207968103099432047374677543229331540706277526947368767969434429565383119554767303697722958157645742281397722992120606265055289
q = 149964660518396798660782215517197000054264985822608779681144262791391323000835825727277636178043097046988857828384650158626906824855399961360412435818827649355003329726451846544435103030378220357694459358803967598155925736581896165952170564324730092516286266118841005062382011803493961966912439338500328959743
e = 20912068408571562329765690555061159289641629285082404210189101064954330953315593257557260077525915152641073106397431556875680393639301995231540409600633056790407217644109479375811025952060540276714119842291972532268686811648476477127818267411283106601195166099848608860814911133056759210847640244371352294577674757844032344743192797680553522630615249481210459669536735468283778508143359159893770374788694416907786510825727199111604249000530550012491935109887922826382346971222271516625157446929215544796309806757863550058676780306722906895167581167203804721314732494889662194466565293268848629536070864750745494338531
e = 65537
n = p*q
d = inverse(e, (p-1)*(q-1))
key = RSA.construct(map(int, (n,e,d)))
print(key.exportKey().decode('utf-8'))
RSAPrivateKey ::= SEQUENCE {
version Version,
modulus INTEGER, -- n
publicExponent INTEGER, -- e
privateExponent INTEGER, -- d
prime1 INTEGER, -- p
prime2 INTEGER, -- q
exponent1 INTEGER, -- d mod (p-1)
exponent2 INTEGER, -- d mod (q-1)
coefficient INTEGER, -- (inverse of q) mod p
otherPrimeInfos OtherPrimeInfos OPTIONAL
}
private1.pem.unencryptedの場合、以下のように対応することが分かります。
version = 00
modulus(n) = A5A7CE44462E8AC6E4DA5E8A8D58E003B8267568B358106CF06412884CEEB7CC4251C2CCE2DB74689D1AFA109BDE9762402E81D96CB6C8C6C5AEBC8D45A96BF214A618B499A8C6134035C5039BF9A39BC47190E4CC4560CB75AB8D63635CDEE8E50F5815B29180CC51A4C8CF76A8BBE6E61C68ACA385FDF99E712B10A6BE7ED794CF27540B7AA00F59DA5579040A9B3B7C23E9E22A15C29EB0C060B96D1F48D1C458E2C412512962CE5AF885237B6138DF6C9E85D101C266C3B80B02FF97D6FDE46598E19E3FA1DF2C56BD34ADDFE716569A2ED42C6442BF2DB5E9A51CC2D7DD4497717DDD9A8A66AE281E1A2ABF7DF7A59779B499CC0F8167A19E3CA5C9BBE3
publicExponent(e) = 010001
privateExponent(d) = 96B06F11EC45AA380336218A27CA10FD5126AAE6F33DC8B35079B7E20519A2584C7BD3984D45143F95AA548F873A94BAEB6762F745CD801650FD02C7FFF67E1B586D3F4C09FB5D3365D583C224C091F3C05F0E4F1302896A8B3FE2FDE6053540E61D6F234DACCE5D0E67B7C4014CBCA0EDF229C5E17AA1EDD01361F963B525EBBEAA2BAB232940ACFFB08F2683A291BF28F803B37360CE3A8B4875D1DAEB34A6D0A90D9E4B8EA29AEC615B71329221B3C2F46DCA19B80B96540BCE135716DC46E5B3B320257B0593BFF2C74D0388E20A4597EF0AACA32340F569B0BB53ED9DA811E5959A89800624EEA057224254D20C9C257FD08A570F6F6E946F7D20734F01
prime1(p) = C6941FD1FD3DEDF69080356F0C76E2497F2569519BCEFFF5DC72B63FAE2F352ED1F4EFB254FCDDB45979216C9164FF946234A3EFDD0143747F55380E003BECCED49D04A8E2A1F35586C3A15C3B81EE1FB18D8528C02C2A0FA29209E4621C316DFA4FF4FA400D3EC4AA900F631AF61E6BB6F0D1EDA6F2FBF8E10E15B51B7D171D
prime(q) = D58E882C1BE40C480E11A517C3DEEECDBBE5FD02EBE7A9F1F5F4E47CF8CD1B6443888238CB4A3424913487744D5DE2EC32D7DAFCB4A53B23DFED9A1261B3E9C7FE5AF4534908D0F700ED15402598C2E0C36880D8C999BA8A560D963728AE21E02D39FCDB6D118E88175BD89033B08D2958A7E8D0EFA7A26A2A7E3E1D1D42AEFF
exponent1(d mod (p-1)) = 4CDC0C2CE4CDD18AFB8704278535868457F80CF98F4AE17B31E61C702D650C3AA0FD22C16D6FAA0822116644754A183A40808B6B4DA92D88ABB83A48010330B72547D903DD243DE0BE967DA00B5050F0677295359E9BF973AFC2C29D68F3EC95DAAA93F14055601412C84B8C5A652485207BB965389717BBCEAFFAEAEC46D069
exponent2(d mod (q-1)) = 71C005D058DAD39FDDBE904D644B6EAFAF1205FE74616528387644EE3C28241AF7CDD26F25F95464D5E340F335F278588F8C625C906C22602D7A85C29CC0141A2EE58B9681246D09E438644552C157AC18E9A517D3EA4A6E3CFFE7AF61BFBED385C38967E7649EA2E6AE496025E83888796C969A13CD1AB9AA00AC5D1DA4D349
coefficient((inverse of q) mod p) = 79F4EEF19181750A4313AF2495331ED2AB837D54CB2D9447FC40A5B92383ACB44F28186405DD8C400650B1E87DB84981CC250C6CE00120319CD6AD00CEE30E48D59F6E1983AEBA91D57A47DBF072A0A13CAEE426DED9E5635895780746DADAACD568E70B7462FBA117CE8F869D447CBBF2753CCE8FC6BD4934EE4D112EEB9AA2
q の値で素数であることの確認
以下のPythonのファイルを用意します。
def is_prime(q):
q = abs(q)
if q == 2: return True
if q < 2 or q&1 == 0: return False
return pow(2, q-1, q) == 1
def main():
x = 149964660518396798660782215517197000054264985822608779681144262791391323000835825727277636178043097046988857828384650158626906824855399961360412435818827649355003329726451846544435103030378220357694459358803967598155925736581896165952170564324730092516286266118841005062382011803493961966912439338500328959743
z = is_prime(x)
print z
if __name__=="__main__":
main()
