乘数加密法
在讲仿射加密法之前，我们先说乘数加密法
凯撒加密法中，加密和解密符号涉及把他们转化成数字，加上或者减去密钥，再把新的数字换成符号
如果我们不使用加而用乘法，可以吗？当然，只需要用mod运算把一个大的整数唯一映射到一个字符
就好了
乘数加密法的优势是，可以使用一个很大的key, 而不局限于凯撒加密法的密钥空间 0~25
缺点是A总是映射到A，为了克服这种缺点，我们再使用一次凯撒加密法即可
缺点是并不是所有key都能使用
比如若选择key=8,则有
A
B
C
D
E
F
G
H
I
J
K
L
M
A
I
Q
Y
G
O
W
E
M
U
C
K
S
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
A
I
Q
Y
G
O
W
E
M
U
C
K
S
这甚至不是一一映射！！没有用
仿射加密法
乘数加密法+凯撒加密法 = 仿射加密法
keyA应当满足一定条件：
密钥A数字和符号集的大小必须互质，也就是说gcd(密钥A, 符号集大小) = 1
模算术运算 加法and乘法
模b运算中，整数x的乘法逆元是y：使得（x × y）mod b = 1
模b运算中，整数x的加法逆元是y：使得（x + y）mod b = 0
一般来说，只有当一个整数与n互素的时候，他才会在Zn中存在一个乘法逆元
使用扩展欧几里得算法可以方便地找到一个数字的模逆，python实现：
def findModInverse(a, m):
# Returns the modular inverse of a % m, which is
# the number x such that ax % m = 1
# 如果a 和 m 不互质，则不存在模逆
if gcd(a, m) != 1:
return None # no mod inverse if a & m aren't relatively prime
# Calculate using the Extended Euclidean Algorithm:
u1, u2, u3 = 1, 0, a
v1, v2, v3 = 0, 1, m
while v3 != 0:
q = u3 // v3 # // is the integer division operator
v1, v2, v3, u1, u2, u3 = (u1 - q v1), (u2 - q v2), (u3 - q v3), v1, v2, v3
return u1 % m
输出：
15
]> cryptomath.findModInverse(37, 41)
10
]> cryptomath.findModInverse(8953851, 26)
17
]>
前面是开胃菜，接下来要展示点真正下饭的东西了！
仿射加密法
我们要使用两个密钥，记住一个数是方便地。使用简单的数学技巧将一个数分解成两个key
如使用key = 2023 则：
keyA = key // len(密文符号集) 2023 // 95 = 21
keyB = key % len(密文符号集) 2023 % 95 = 28
显然 keyA len(密文符号集) + keyB = key (21 95) + 28 = 2023
这两个密钥显然不能在程序中出差错，所以用元组保存是可取的。
元组是python中的一种数据类型。可以通过索引和分片来访问，但是很重要的一点，元组里面的值不能被更改！
对于生成的密钥，我们要确认其可行性：
keyA不能为1
keyB不能为0
keyA、keyB必须大于0，keyB不大于ken(密文符号集) -1
最重要的一点，满足keyA必须与密文符号集的大小互质，才能使得这是一个一一映射。
仿射加密算法
# Affine Cipher
# (BSD Licensed)
'''
1.The affine cipher can be thought of as the combination of which two other ciphers?
2.What is a tuple?
3.How is a tuple different from a list?
4.Why does having Key A be 1 make the affine cipher weak?
5.Why does having Key B be 0 make the affine cipher weak?
answer
1.The shift and multiplicative ciphers.
2.A data type in Python similar to lists, except immutable.
3.Tuples are immutable, meaning they cannot have their items changed.
4.Because multiplying the symbol's number by 1 does not change it.
5.Because adding 0 to the symbol's number does not change it.
'''
import sys, pyperclip, cryptomath, random
SYMBOLS = """ !"#$%&'()+,-./0123456789:;?@ABCDEFGHIJKLMNOPQRSTUVWXYZ【\】^_`abcdefghijklmnopqrstuvwxyz{|}~""" # note the space at the front
def main():
myMessage = """"A computer would deserve to be called intelligent if it could deceive a human into believing that it was human." -Alan Turing"""
myKey = 2023
myMode = 'encrypt' # set to 'encrypt' or 'decrypt'
if myMode == 'encrypt':
translated = encryptMessage(myKey, myMessage)
elif myMode == 'decrypt':
translated = decryptMessage(myKey, myMessage)
print('Key: %s' % (myKey))
print('%sed text:' % (myMode.title()))
print(translated)
pyperclip.copy(translated)
print('Full %sed text copied to clipboard.' % (myMode))
def getKeyParts(key):
keyA = key // len(SYMBOLS)
keyB = key % len(SYMBOLS)
return (keyA, keyB)
def checkKeys(keyA, keyB, mode):
if keyA == 1 and mode == 'encrypt':
sys.exit('The affine cipher becomes incredibly weak when key A is set to 1. Choose a different key.')
if keyB == 0 and mode == 'encrypt':
sys.exit('The affine cipher becomes incredibly weak when key B is set to 0. Choose a different key.')
if keyA < 0 or keyB < 0 or keyB > len(SYMBOLS) - 1:
sys.exit('Key A must be greater than 0 and Key B must be between 0 and %s.' % (len(SYMBOLS) - 1))
if cryptomath.gcd(keyA, len(SYMBOLS)) != 1:
sys.exit('Key A (%s) and the symbol set size (%s) are not relatively prime. Choose a different key.' % (keyA, len(SYMBOLS)))
def encryptMessage(key, message):
keyA, keyB = getKeyParts(key)
checkKeys(keyA, keyB, 'encrypt')
ciphertext = ''
for symbol in message:
if symbol in SYMBOLS:
# encrypt this symbol
symIndex = SYMBOLS.find(symbol)
# 乘数加密 + 凯撒加密 = 仿射加密方法
ciphertext += SYMBOLS【(symIndex keyA + keyB) % len(SYMBOLS)】
else:
#如果在符号集中没有这个特殊符号，不能舍弃，保留，保证密文和明文等长
ciphertext += symbol # just append this symbol unencrypted
return ciphertext
def decryptMessage(key, message):
keyA, keyB = getKeyParts(key)
checkKeys(keyA, keyB, 'decrypt')
plaintext = ''
#需要找到keyA的乘法模逆
modInverseOfKeyA = cryptomath.findModInverse(keyA, len(SYMBOLS))
for symbol in message:
if symbol in SYMBOLS:
# decrypt this symbol
symIndex = SYMBOLS.find(symbol)
plaintext += SYMBOLS【(symIndex - keyB) modInverseOfKeyA % len(SYMBOLS)】
else:
plaintext += symbol # just append this symbol undecrypted
return plaintext
def getRandomKey():
while True:
keyA = random.randint(2, len(SYMBOLS))
keyB = random.randint(2, len(SYMBOLS))
if cryptomath.gcd(keyA, len(SYMBOLS)) == 1:
return keyA len(SYMBOLS) + keyB
# If affineCipher.py is run (instead of imported as a module) call
# the main() function.
if name == 'main':
main()
输出：
Key: 2023
Encrypted text:
fX}(rTH
Full encrypted text copied to clipboard.
PS D:\PiaYie\jczhang\密码学\py密码学编程教学代码
暴力破译仿射密码
那么，暴力破译的话，就必须明白仿射加密法有多少个密钥？
keyB: “回调”受限：1 ~ len(密文符号集)
keyA： 与len(密文符号集)互质的数，是否也会出现“回调”的情况？
//代码效果参考：http://www.jhylw.com.cn/595335755.html
SYMBOLS = """ !"#$%&'() +,-./0123456789:;?@ABCDEFGHIJKLMNOPQRSTUVWXYZ【\】^_`abcdefghijklmnopqrstuvwxyz{|}~""" # note the space at the frontlen(SYMBOLS) = 95
测试一下
# This program proves that the keyspace of the affine cipher is limited
# to len(SYMBOLS) ^ 2.
import affineCipher, cryptomath
message = 'Make things as simple as possible, but not simpler.'
for keyA in range(2, 100):
key = keyA len(affineCipher.SYMBOLS) + 1
if cryptomath.gcd(keyA, len(affineCipher.SYMBOLS)) == 1:
print(keyA, affineCipher.encryptMessage(key, message))
输出：
n-2020.7.96456\pythonFiles\lib\python\debugpy\launcher' '49271' '--' 'd:\PiaYie\jczhang\SJTU\密码学\py密码学编程教学代码\affineKeyTest.py'
2 {DXL!jRT^Ph!Dh!hT\bZL!Dh!bhhTFZL9!Flj!^j!hT\bZLf=
3 I&D2!;>M8!&!>JSG2!&!SP\>)G2E!)b!MP!>JSG2YK
4 vg0w!T$(@T!P(8D4wLY
6 q+gC!>U【yO8!+8!8【s&mC!+8!& 88【1mCi!1D>!y >!8【s&mC2u
7 ?lS)!3>Eh7,!l,!,EavZ)!l,!vo,,EsZ)u!s:3!ho3!,EavZ)%$
8 lN?n!('/W~ !N ! /OgGn!N !g /VGn"!V0(!W(! /OgGnw2
9 :0+T!|oxFfs!0s!sx=X4T!0s!XOssx94T.!9&|!FO|!sx=X4Tj@
11 5Sb !fAL$6【!S【!【Lx:m !S【!:/【【L^m F!^qf!$/f!【Lx:m P\
12 b5Ne!【*6r}O!5O!O6f+Ze!5O!+~OO6AZeR!Ag【!r~【!O6f+ZeCj
13 0v:K!Pr aeC!vC!C T{GK!vC!{nCC $GK^!$】P!anP!C T{GK6x
14 】X&1!E【iPM7!X7!7iBl41!X7!l^77if41j!fSE!P^E!7iBl41)'
16 X{】!/-=.|~!{~!~=}Nm!{~!N>~~=,m#!,?/!.>/!~=}Nm\nC
17 &】IB!$u'|dr!】r!r'k?ZB!】r!?.rr'nZB/!n5$!|.$!r'k?ZBaQ
18 S?5(!x^pkLf!?f!fpY0G(!?f!0}ffpQG(;!Q+x!k}x!fpY0G(T
21 {DX9!Wx.8cB!DB!B.#bm9!DB!bMBB.Ym9!YlW!8MW!B.#bm9-
22 I&D~!Law'K6!&6!6wpSZ~!&6!S=66w<Z~k!<bL!'=L!6wpSZ~ 8
23 vg0d!AJau3!g!a^DGd!g!D-**a~Gdw!~XA!u-A!a^DGdrF
24 DI{J!63Kdz}!I}!}KL54J!I}!5|}}Ka4J$!aN6!d|6!}KL54JeT
26 ?lSu! d~BJe!le!e~(vmu!le!v\ee~'mu<!': !B\ !e~(vmuKp
27 lN?【!tMh12Y!NY!YhugZ【!NY!gLYYhiZ【H!i0t!1Lt!YhugZ【>~
28 :0+A!i6R yM!0M!MRcXGA!0M!X
29 gqv'!^~<naA!qA!A<QI4'!qA!I,AA</4'`!/{^!n,^!A
31 b5NR!HPoL1)!5)!)o-+mR!5)!+k))oTmRx!TgH!LkH!)o-+mRiW
32 0v:8!=9Y;x|!v|!|Yz{Z8!v|!{【||Y7Z8%!7】=!;【=!|Yz{Z8\e
33 】X&}!2"C`p!Xp!pChlG}!Xp!lKppCyG}1!yS2!K2!pChlG}Os
34 +:qc!'j-xHd!:d!d-V】4c!:d!】;dd-\4c=!\I'!x;'!d-V】4cB"
36 &】I/!p<VwL!】L!L2?m/!】L!?zLL"m/U!"5p!Vzp!L2?m/(>
37 S?5t!e%JE@!?@!@J 0Zt!?@!0j@@JdZta!d+e!Eje!@J 0ZtzL
39 Nbl@!OV}#/(!b(!(}【q4@!b(!qJ((}4@y!vO!#JO!(}【q4@h</p> <p>41 I&Dk!9(Q^o!&o!oQ7Smk!&o!SooQOmk2!Ob9!`9!oQ7SmkF%
42 vg0Q!.p;OFc!gc!c;%DZQ!gc!Dycc;2ZQ>!2X.!Oy.!c;%DZQ93
43 DI{7!#Y%>.W!IW!W%r5G7!IW!5iWW%tG7J!tN#!>i#!W%r5G7,A
44 q+g|!wBn-uK!+K!Kn&4|!+K!&YKKnW4|V!WDw!-Yw!Kn&4|~O
46 lN?H!asBjE3!N3!3BgmHdk
47 :0+.!V\,Y-'!0'!',XZ.!0'!X)'',Z.z!&V!Y)V!',XZ.Wy
48 gqvs!KEuHtz!qz!zuwIGs!qz!IxzzuBGs'!B{K!HxK!zuwIGsJ(
49 5SbY!@._7\n!Sn!ne:4Y!Sn!:hnn%4Y3!%q@!7h@!n_e:4Y=6
51 0v:%!_3t,V!vV!V3A{m%!vV!{HVV3Jm%K!J】!tH!V3A{m%#R
52 】X&j!~H|csJ!XJ!J|/lZj!XJ!l8JJ|-ZjW!-S~!c8~!J|/lZju`
53 +:qP!s1fR【>!:>!>f|】GP!:>!】(]foGPc!oIs!R(s!>f|】GPhn
54 X{】6!hyPAC2!{2!2PjN46!{2!Nw22PR46o!R?h!Awh!2PjN46【|
56 S?5a!RK$~ry!?y!y$F0ma!?y!0Wyy$wma(!w+R!~WR!y$F0maA9
58 Nbl-!|W\Ba!ba!aW"qG-!ba!q7aaW=G-@!=v
59 {DXr!1eAKU!DU!UAob4r!DU!b'UUA 4rL! l1!K'1!UAob4ryc
61 vg0>!z7t)Y=!g=!=tKDm>!g=!Df==tEm>d!EXz!)fz!=tKDm>_
62 DI{$!o
