python - Cocoa (Obj-C) 中使用大数的 Mod 函数

Question

大家好，

我向我的 10 年级 IT 类展示了这个网站:

http://blogs.msdn.com/b/plankytronixx/archive/2010/10/23/crypto-primer-understanding-encryption-public-private-key-signatures-and-certificates.aspx

教他们有关公钥私钥加密的知识。最初，我要求他们在 Excel 中自行重现计算结果，但事实证明，当涉及到此类数字时，Excel 严重受到攻击。

我决定用 Python 和 Obj-C 为他们演示。整个Python代码如下:

from Tkinter import *

def appClose():
sys.exit()

def setup_algorithm():
p = int(pText.get())
q = int(qText.get())
e = int(eText.get())
N = p*q
nText.config(text=str(N))
eText2.config(text=str(e))
modValue = (p-1)*(q-1)
print 'Mod value = ', modValue

result = 0
d = 0
while result != 1:
    d += 1
    if d > 999:
        result = 1
    else:
        result = divmod((e * d),modValue)[1]
dText.config(text=str(d))

def encrypt():
plainTextValue = int(plainIn.get())
N = int(nText.cget("text"))
e = int(eText2.cget("text"))

cipher = pow(plainTextValue, e) % N

cipherOut.insert(0,cipher)

def decrypt():
cipherTextValue = int(cipherIn.get())
N = int(nText.cget("text"))
d = int(dText.cget("text"))

plain = pow(cipherTextValue, d) % N

plainOut.insert(0, plain)


main = Tk()
main.title('Public Private Key Encryption Demo')
main.geometry('700x600+200+100')

pLabel = Label(main, text='p = ')
pLabel.grid(row=1, column=1, padx=10, pady=10)
qLabel = Label(main, text='q = ')
qLabel.grid(row=2, column=1, padx=10, pady=10)
eLabel = Label(main, text='e = ')
eLabel.grid(row=3, column=1, padx=10, pady=10)
pText = Entry(main, width=5)
pText.grid(row=1, column=2, padx=10)
qText = Entry(main, width=5)
qText.grid(row=2, column=2, padx=10)
eText = Entry(main, width=5)
eText.grid(row=3, column=2, padx=10)

space1 = Label(main)
space1.grid(row=1, column=3, padx=50)

pubLabel = Label(main, text='Public key details')
pubLabel.grid(row=1, column=4, padx=10, columnspan=2)
privLabel = Label(main, text='Private key details')
privLabel.grid(row=4, column=4, padx=10, pady=10, columnspan=2)

nLabel = Label(main, text='N = ')
nLabel.grid(row=2, column=4)
eLabel2 = Label(main, text='e = ')
eLabel2.grid(row=3, column=4)
nText = Label(main)
nText.grid(row=2, column=5, padx=10)


eText2 = Label(main)
eText2.grid(row=3, column=5, padx=10)

dLabel = Label(main, text='d = ')
dLabel.grid(row=5, column=4)
dText = Label(main)
dText.grid(row=5, column=5, padx=10)

space2 = Label(main)
space2.grid(row=6, column=1, pady=20)

lbPlainIn = Label(main, text='Plaintext In')
lbPlainIn.grid(row=7, column=1)
plainIn = Entry(main)
plainIn.grid(row=7, column=2)
lbCipherOut = Label(main, text='Ciphertext Out')
lbCipherOut.grid(row=9, column=1)
cipherOut = Entry(main)
cipherOut.grid(row=9, column=2)

lbCipherIn = Label(main, text='Ciphertext In')
lbCipherIn.grid(row=7, column=4)
cipherIn = Entry(main)
cipherIn.grid(row=7, column=5)
lbPlainOut = Label(main, text='Plaintext Out')
lbPlainOut.grid(row=9, column=4)
plainOut = Entry(main)
plainOut.grid(row=9, column=5)

space3 = Label(main)
space3.grid(row=10, column=0, pady=20)

pbClose = Button(main, text='Close', command=appClose)
pbClose.grid(row=10, column=3)

pbSetup = Button(main, text='Setup', command=setup_algorithm)
pbSetup.grid(row=4, column=2)

pbEncrypt = Button(main, text='Encrypt', command=encrypt)
pbEncrypt.grid(row=8, column=2, pady=10)

pbDecrypt = Button(main, text='Decrypt', command=decrypt)
pbDecrypt.grid(row=8, column=5, pady=10)
mainloop()

我对大量代码表示歉意。我提请您注意两种方法:加密和解密。在这种情况下，它们的工作方式与广告中的完全一样，并且可以重现网站上显示的计算结果。

当我在 Obj-C 中编写相同的代码时:

#import "UIController.h"

@implementation UIController

- (id)init {
    self = [super init];
    if (self) {
        // Initialize self.
        NSLog(@"Init ran");
    }
    return self;
}

-(void)awakeFromNib
{
    [txtNValue setStringValue:@"187"];
    [txtEValue2 setStringValue:@"7"];
    [txtDValue setStringValue:@"23"];
}

-(int)findDValue:(int)p :(int)q :(int)e
{
    NSLog(@"Find d value");
    int d = 0;
    int result;

    while (d < 1000)
    {
        result = (e * d) % ((p-1)*(q-1));
        if (result == 1) {
            return d;
        }
        d++;
    }

    return d;
}

-(IBAction)setupAlgorithm:(id)sender
{
    int p = [[txtPValue stringValue]intValue];
    int q = [[txtQValue stringValue]intValue];
    int e = [[txtEValue stringValue]intValue];

    int N = p * q;

    [txtNValue setStringValue:[NSString stringWithFormat:@"%i", N]];
    [txtEValue2 setStringValue:[NSString stringWithFormat:@"%i", e]];

    int d = [self findDValue:p:q:e];
    NSLog(@"d = %i", d);
    [txtDValue setStringValue:[NSString stringWithFormat:@"%i", d]];
}

-(IBAction)encrypt:(id)sender
{
    double plainTextValue = [[txtPlainInput stringValue]doubleValue];
    double e = [[txtEValue2 stringValue]doubleValue];
    double N = [[txtNValue stringValue]doubleValue];

    NSLog(@"N = %f and e = %f", N, e);

    double cipher = fmod(pow(plainTextValue, e), N);
    NSLog(@"%f", pow(plainTextValue, e));

    [txtCipherOutput setStringValue:[NSString stringWithFormat:@"%f", cipher]];

}
-(IBAction)decrypt:(id)sender
{
    double cipherTextValue = [[txtCipherInput stringValue]doubleValue];
    double d = [[txtDValue stringValue]doubleValue];
    double N = [[txtNValue stringValue]doubleValue];
    NSLog(@"N = %f and d = %f", N, d);

    double plain = fmod(pow(cipherTextValue, d), N);
    NSLog(@"%f", pow(cipherTextValue, d));

    [txtPlainOutput setStringValue:[NSString stringWithFormat:@"%f", plain]];

}

@end

加密端有效，“88”被加密为“11”，但反之则不起作用。解密时，“11”解密为“149”。 pow() 计算的结果是正确的，所以它一定与 Obj-C 中的 fmod() 计算有关，但我不知道为什么。

谁能给我解释一下吗？

谢谢

Answer 1

所以基本上，11²³ 需要太多的位才能容纳长 double 的尾数。幸运的是，有一个简单的算法可以做到 modular exponentiation这依赖于这样一个事实:

(a * b) % m == (a * (b % m)) % m

维基百科页面上有一个名为 Right to Left Binary method 的算法。其工作时间为 O(n)，其中 n 是指数中的位数。该函数的 C 版本如下所示(注意未编译或测试)。

unsigned int 
modular_pow(unsigned int base, unsigned int exponent, unsigned int modulus)
{
    unsigned int result = 1;
    base = base % modulus;
    while (exponent > 0)
    {
        if (exponent % 2 == 1)
        {
           result = (result * base) % modulus;
        }
        exponent /= 2;
        base = (base * base) % modulus;
    }
    return result;
}

请注意，许多大数库都有此函数的内置版本。例如，Java 的 BigInteger 有一个名为 modPow() 的方法。