第3章 密码学基础

第3章密码学基础l

密码学的基本概念和术语l

对称和非对称密码的区别l

古典密码学的基本方法l

掌握DES算法、AES算法RSA算法的基本原理13.1密码学概述3.1.1密码学的发展史恺撒（Caesar）密码一种简单易行的单字母替代密码

维吉尼亚密码（Vigenere

cypher）多表加密的替代密码

“恩格玛（Enigma）”密码机

DES（数据加密标准）美国国家标准局颁布的国家标准密码学历史上一个具有里程碑意义的事件

23.1.1密码学的发展史（续）公开密钥密码

密码学的一场革命量子密码学

3密码学的发展史大体上可以归结为三个阶段

第一阶段：1949年之前，密码学还不是科学,而是艺术。

第二阶段：1949～1975年，密码学成为科学。

第三阶段：1976年以后，密码学的新方向——公钥密码学。（公钥密码使得发送端和接收端无密钥传输的保密通信成为可能。）

43.1.2密码系统一个密码系统被定义为一对数据变换：加密变换：将明文和加密密钥作为输入，输出密文；解密变换：将密文和解密密钥作为输入，输出明文；密钥是变换中的一个参数。5简单加密系统模型简单地说它就是一组含有参数K的变换E。设已知消息m，通过变换Ek得密文C，即，这个过程称为加密，E为加密算法，k不同，密文C亦不同。传统的保密通信机制：EncipherPlaintextCiphertextKeysDecipherC=Ek(m)发方：m收方：mkk（公共信道）加密E解密D（秘密信道）6理论安全和实际安全

TheoreticalSecurity(orPerfectSecurity)andPracticalSecure(orComputationallySecure)理论安全，或无条件安全：攻击者无论截获多少密文，都无法得到足够的信息来唯一地决定明文。Shannon用理论证明：欲达理论安全，加密密钥长度必须大于等于明文长度，密钥只用一次，用完即丢，即一次一密，One-timePad，不实用。实际安全，或计算上安全：如果攻击者拥有无限资源，任何密码系统都是可以被破译的；但是，在有限的资源范围内，攻击者都不能通过系统地分析方法来破解系统，则称这个系统是计算上安全的或破译这个系统是计算上不可行（ComputationallyInfeasible）。

78密码体制

加密系统采用的基本工作方式称为密码体制。密码体制的基本要素是密码算法和密钥。密码算法是一些公式、法则或程序；密钥是密码算法中的控制参数。通常一个密码体制可以表达为一个五元组（P，C，K，E，D），其中：（1）P是可能明文的有限集称为明文空间（2）C是可能密文的有限集称为密文空间（3）K是一切可能密钥构成的有限集称为密钥空间（4）对于密钥空间的任一密钥有一个k∈K，则有C＝Ek(P)，P＝Dk(C)＝Dk(Ek(P))，或者Dk＝Ek－1，且Ek＝Dk－1。93.1.3密码的分类1、按应用的技术或历史发展阶段划分：手工密码机械密码电子机内乱密码计算机密码2、按保密程度划分：理论上保密的密码实际上保密的密码不保密的密码103.1.3密码的分类（续）

3、按密钥方式划分：对称密码体制(SymmetricSystem,One-keySystem,Secret-keySystem)加密密钥和解密密钥相同，或者一个密钥可以从另一个导出，能加密就能解密，加密能力和解密能力是结合在一起的，开放性差。非对称密码体制(AsymmetricSystem,Two-keySystem,Public-keySystem)加密密钥和解密密钥不相同，从一个密钥导出另一个密钥是计算上不可行的，加密能力和解密能力是分开的，开放性好。113.1.3密码的分类（续）

4、按明文形态：模拟型密码数字型密码5、按编制原理划分：移位、代替和置换以及它们的组合形式123.1.4近代加密技术

1、对称加密算法对称加密算法（synmetricalgorithm），也称为传统密码算法，其加密密钥与解密密钥相同或很容易相互推算出来，因此也称之为秘密密钥算法或单钥算法。对称算法分为两类一类称为序列密码算法（streamcipher）：以明文中的单个位（有时是字节）为单位进行运算；另一种称为分组密码算法（blockcipher）：以明文中的一组位为单位进行运算。加密过程中会用到两种技术：混乱（confusion）：改变信息块使输出位和输入位无明显的统计关系。扩散（diffusion）：将明文位和密钥的效应传播到密文的其他位。13对称加密系统由以下五部分组成:Plaintext：明文Encryptionalgorithm：加密算法SecretKey：密钥Ciphertext：密文Decryptionalgorithm：解密算法加密算法必须足够强大，使破译者不能仅根据密文破译消息；Securitydependsonthesecrecyofthekey,notthesecrecyofthealgorithm.对称密码的模型141、对称加密算法（续）对称加密算法的主要优点是运算速度快，硬件容易实现；其缺点是密钥的分发与管理比较困难，特别是当通信的人数增加时，密钥数目急剧膨胀。如当n个人互相之间通信时，需要有n(n-1)/2个密钥。1516Requirementstworequirementsforsecureuseofsymmetricencryption:astrongencryptionalgorithmasecretkeyknownonlytosender/receiver Y=EK(X) X=DK(Y)assumeencryptionalgorithmisknownimpliesasecurechanneltodistributekey17Y=Ek(X)X=Dk(Y)182、非对称加密体制非对称加密算法（AsynmetricAlgorithm）也称公开密钥算法（PublicKeyAlgorithm）。公开密钥体制把信息的加密密钥和解密密钥分离，通信的每一方都拥有这样的一对密钥。其中加密密钥可以像电话号码一样对外公开，由发送方用来加密要发送的原始数据；解密密钥则由接收方秘密保存，作为解密时的私用密钥。19公开密钥密码系统的原理对称密码体制的问题加密能力与解密能力是捆绑在一起的密钥更换、传递和交换需要可靠信道如有N用户，则需要C=N(N-1)/2个密钥，n=1000时，C(1000,2)≈500000,管理困难无法满足不相识的人之间通信的保密要求不能实现数字签名非对称密码体制的基本特点加密能力与解密能力是分开的密钥分发简单需要保存的密钥量大大减少，N个用户只需要N个可满足不相识的人之间保密通信可以实现数字签名20公开密钥加密算法的核心是一种特殊的数学函数——单向陷门函数（Trap-DoorOneWayFunction），即该函数从一个方向求值是容易的，但是其逆变换却是极其困难。其通用表示为：Ek1(M)=CDk2(C)=MDk2(Ek1(M))=M公开秘钥加密算法可用于加密和认证21公开密钥加密过程22公开密钥认证过程23公开密钥密码系统:保密24公开密钥密码系统:认证25公开密钥密码系统:保密和认证262、非对称加密体制（续）公开密钥体制最大的优点就是不需要对密钥通信进行保密，所需传输的只有公开密钥。这种密钥体制还可以用于数字签名。公开密钥体制的缺陷在于其加密和解密的运算时间比较长，这在一定程度上限制了它的应用范围。272、非对称加密体制（续）三个不同方面的用途：数据的加密解密：RSA数字签名：RSA、DSS密钥交换：RSA、Diffie-Hellman28密码编码学(Cryptography)密码编码系统根据以下三个独立方面进行分类：用于将明文转换为密文操作的类型：替代和置换所使用的密钥的数量：对称密码体制，单钥系统、秘密密钥系统非对称密码体制，双钥系统、公开密钥系统明文处理的方式：分组加密和流加密密码分析学(Cryptanalysis)试图破译密文得到明文或试图获得密钥的过程为密码分析，密码破译的策略取决于加密方法及可供破译者使用的信息。Cryptology密码学293.1.5密码的破译不同的密码系统可能使用不同长度的钥匙。在其他条件相同的情况下，钥匙越长，破译密码就越困难，密码系统就越可靠。303.1.5密码的破译（续）1、密钥的穷尽搜索尝试所有可能的钥匙组合。2、密码分析利用数学方法破译密文或找到钥匙的方法称为密码分析。有两个基本目标：利用密文发现明文利用密文发现钥匙常见的有：已知明文的破译方法

选定明文的破译方法

差别比较分析法

31BruteForceSearchalwayspossibletosimplytryeverykeymostbasicattack,proportionaltokeysizeassumeeitherknow/recogniseplaintext32333.1.5密码的破译（续）真正的加密安全性，必须要建立在公开和广泛的同行鉴定、检查的基础之上。3、其它密码破译方法针对人机系统的弱点进行攻击以达到其目的。

343.2古典密码学3.2.1代换密码

代换密码的特点是：改变明文内容的表示形式，保持内容元素之间相对位置不变。1、移位密码——凯撒密码（k=3）移位密码基于数论中的模运算。因为英文有26个字母，故可将移位密码定义如下：令P={A,B,C,……Z}，C={A,B,C,……Z},K={0，1，2,……25}，加密变换：Ek（x）=（x+k）mod26解密变换：Dk（y）=（y-k）mod26352、单表代换密码单表代换密码的基本思想是：列出明文字母与密文字母的一一对应关系。

明文AbcDefghijklm密文WJANDYUQIBCEF明文nopQrstuvwxyz密文GHKLMOPRSTVXZ例如：明文为networksecurity,则相就的密文为：GDPTHMCODARMIPX。363、多表替换密码Vigenere密码是一种典型的多表替换密码算法。算法如下：设密钥K=k1k2……kn,明文M=m1m2……mn,加密变换:ci≡（mi+ki）mod26,i=1,2,……,n解密变换：mi≡（ci-ki）mod26,i=1,2,……,n例如：明文X=cipherblock,密钥为：hit则把明文划分成长度为3的序列：cipherblock每个序列中的字母分别与密钥序列中相应字母项加并进行模26运算，得密文：JQIOMKITHJS373.2.2置换密码置换密码的特点是保持明文的所有字母不变，只是利用置换打乱明文字母出现的位置。置换密码体制定义如下：令m为一正整数，P=C={A,B,C,……Z}，对任意的置换π（密钥），定义:

加密变换：Eπ（x1,x2,……,xm）=（xπ（1）,xπ（2）……,xπ（m））,

解密变换：Dπ（y1,y2,……,ym）=（xπ-1（1）,xπ-1

（2）……,xπ-1

（m））,

置换密码也不能掩盖字母的统计规律，因而不能抵御基于统计的密码分析方法的攻击。38置换技术(Transpositionorpermutation)改变明文内容元素的相对位置，保持内容的表现形式不变。一维变换－矩阵转置二维变换－图形转置DNATSREDNUUOYNAC明文：canyouunderstand密文：codtaueanurnynsd输入输出UUOYNACSREDNNATD密文明文明文：canyouunderstand密文：dnsuaruteodynnac393.3对称密码学3.3.1分组密码概述分组密码是将明文消息编码后的数字序列：b1b2b3b4…划分为长度为n的分组，一个分组表示为：mi=(bj,bj+1,…,bj+n-1)，各个分组在密钥的作用下，变换为等长的数字输出序列ci=(xj,xj+1,xj+2,…,xj+n-1)。40设计分组密码算法时，需要考虑的因素：分组长度n要足够大密钥空间要足够大算法要足够复杂：保证秘钥和明文的充分扩散和混淆加密和解密运算简单，易于实现，差错传播尽可能小41分组密码大多数分组密码基于FeistelCipherStructure分组加密器本质上就是一个巨大的替换器64位的分组就会有264种输入采用了乘积加密器的思想3.3.2Feistel网络42Feistel密码ClaudeShannonandSubstitution-PermutationCiphers1949年，ClaudeShannon

引进了substitution-permutation(S-P)networks的思想，即现代的乘积加密器modernsubstitution-transpositionproductcipher，形成了现代分组加密的基础。S-Pnetworks是基于替代substitution(S-box)和置换permutation(P-box)这两个基本操作的。提供了对明文信息处理所做的confusion和diffusion

。Shannon认为，为了对付基于统计分析的密码破译，必须对明文作confusion(扰乱)和diffusion(扩散)处理，以减少密文的统计特性，为统计分析制造障碍。diffusion–dissipatesstatisticalstructureofplaintextoverbulkofciphertext，明文统计结构扩散消失到大批密文统计特性中，使明文和密文之间统计关系尽量复杂；confusion–makesrelationshipbetweenciphertextandkeyascomplexaspossible，使密文和加密密钥之间的关系尽量复杂。431、扩散和混乱扩散和混乱是由Shannon提出的设计密码系统的两个基本方法，目的是抵抗攻击者对密码的统计分析。扩散就是指将明文的统计特性散布到密文中去

混乱就是使密文和密钥之间的统计关系变得尽可能复杂

442、Feistel网络结构及特点Feistel提出利用乘积密码可获得简单的代换密码。

（1）将明文分组分为左右两个部分：L0，R0，数据的这两部分通过n轮（round）处理后，再结合起来生成密文分组；（2）第i轮处理其上一轮产生的Li-1和Ri-1和K产生的子密钥Ki作为输入。一般说来，子密钥Ki与K不同，相互之间也不同，它是用子密钥生成算法从密钥生成的；（3）每一轮的处理的结构都相同，置换在数据的左半部分进行，其方法是先对数据的右半部分应用处理函数F，然后对函数输出结果和数据的左半部分取异或（XOR）；（4）处理函数F对每轮处理都有相同的通用结构，但由循环子密钥Ki来区分；（5）在置换之后，执行由数据两部分互换构成的交换；（6）解密过程与加密过程基本相同。规则如下：用密文作为算法的输入，但以相反顺序使用子密钥Ki；（7）加密和解密不需要用两种不同的方法。45Feistel密码结构1973年，HorstFeistel提出了基于可逆乘积加密器概念的FeistelCipher：将输入分组分成左右两部分，实施Shannon’s的substitution-permutationnetwork概念对左半部数据实施多回合的替代操作(substitution)对右半部数据和子密钥应用round函数F，其输出与左一半做异或将这两部分进行互换(permutationswapping)

46FeistelCipherEncryptionandDecryption47DES加密算法的一般描述3.3.3DES算法481、算法描述DES算法流程如图3-4所示。首先把明文分成若干个64-bit的分组，算法以一个分组作为输入，通过一个初始置换（IP）将明文分组分成左半部分（L0）和右半部分（R0），各为32-bit。然后进行16轮完全相同的运算，这些运算我们称为函数f，在运算过程中数据与密钥相结合。经过16轮运算后，左、右两部分合在一起经过一个末转换（初始转换的逆置换IP-1），输出一个64-bit的密文分组。495051初始置换IP(InitialPermutation)和逆置换IP-152扩展置换和置换函数53S-盒置换，将48-bit输入转为32-bit的输出，过程如下：48-bit组被分成8个6-bit组，每一个6-bit组作为一个S盒的输入，输出为一个4-bit组。其方式是：6-bit数的首、末两位数决定输出项所在的行；中间的四位决定输出项所在的列。例如：假设第6个S-盒的输入为110101，则输出为第3行第10列的项（行或列的记数从0开始），即输出为4-bit组0001。

S6:12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11,10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8,9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6,4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13,54子密钥的生成

密钥通常表示为64-bit，但每个第8位用作奇偶校验，实际的密钥长度为56-bit。在DES的每一轮运算中，从56-bit密钥产生出不同的48-bit的子密钥（K1,K2……K16）。首先，由64-bit密钥经过一个置换选择（PC-1）选出56-bit并分成两部分（以C、D分别表示这两部分），每部分28位，然后每部分分别循环左移1位或2位（从第1轮到第16轮，相应左移位数分别为：1、1、2、2、2、2、2、2、1、2、2、2、2、2、2、1）。再将生成的56-bit组经过一个另一个置换选择（PC-2），舍掉其中的某8个位并按一定方式改变位的位置，生成一个48-bit的子密钥Ki。

555657DES的解密是加密的逆过程，采用相同算法，但是子密钥使用的次序正好相反。58密钥长度问题56-bit密钥有256=72,057,584,037,927,936≈7.2亿亿之多强力搜索(bruteforcesearch)似乎很困难，20世纪70年代估计要1000－2000年技术进步使穷举搜索成为可能1997年1月29日，RSA公司发起破译RC4、RC5、MD2、MD5，以及DES的活动，破译DES奖励10000美金。明文是：Strongcryptographymakestheworldasaferplace.结果仅搜索了24.6%的密钥空间便得到结果，耗时96天。1998年在一台专用机上(EFF)只要三天时间即可1999年在超级计算机上只要22小时!DES的安全强度593、三重DES如上所言，DES一个致命的缺陷就是密钥长度短，并且对于当前的计算能力，56位的密钥长度已经抗不住穷举攻击，而DES又不支持变长密钥。但算法可以一次使用多个密钥，从而等同于更长的密钥。三重DES算法表示为：C=EK3（DK2（EK1（M）））通常取K3=K1，则上式变为：C=EK1（DK2（EK1（M）））这样对于三重DES的穷举攻击需要2112次，而不是DES的264次了。603.3.5

分组密码的工作模式611.电子密码本模式ElectronicCodebook,ECB明文分成64的分组进行加密，必要时填充，每个分组用同一密钥加密，同样明文分组得相同密文62AdvantagesandLimitationsofECBrepetitionsinmessagemayshowinciphertext

weaknessduetoencryptedmessageblocksbeingindependentmainuseissendingafewblocksofdata632.密码分组链接模式CipherBlockChaining(CBC)加密输入是当前明文分组和前一密文分组的异或，形成一条链，使用相同的密钥，这样每个明文分组的加密函数输入与明文分组之间不再有固定的关系64AdvantagesandLimitationsofCBCeachciphertextblockdependsonallmessageblocksthusachangeinthemessageaffectsallciphertextblocksafterthechangeaswellastheoriginalblockneedInitialValue(IV)knowntosender&receiverhoweverifIVissentintheclear,anattackercanchangebitsofthefirstblock,andchangeIVtocompensatehenceeitherIVmustbeafixedvalue(asinEFTPOS)oritmustbesentencryptedinECBmodebeforerestofmessageatendofmessage,handlepossiblelastshortblockbypaddingeitherwithknownnon-datavalue(egnulls)orpadlastblockwithcountofpadsizeeg.[b1b2b300005]<-3databytes,then5bytespad+count65加密：Ci=Ek

（Pi⊕Ci-1）解密：Pi=Ci-1⊕Dk

（Ci）66密码反馈模式CipherFeedBack(CFB)是一种将DES转化成流密码的技术，不再要求报文被填充成整个分组，可以实时运行，如果要传输一个字符流，每个字符都可以使用面向字符的流密码立刻加密和传输。加密：加密函数的输入是一个64位的移位寄存器，产生初始向量IV。加密函数高端j位与明文P1的第一单元异或，产生j位密文C1进入移位寄存器低端，继续加密，与P2输入异或，如此重复直到所有明文单元都完成加密。解密：采用相同方案，但是使用加密函数而非解密函数。3.密码反馈模式CipherFeedBack(CFB)6768AdvantagesandLimitationsofCFBappropriatewhendataarrivesinbits/bytesmostcommonstreammodelimitationisneedtostallwhiledoblockencryptionaftereveryn-bitsnotethattheblockcipherisusedinencryptionmodeatbothendserrorspropagateforseveralblocksaftertheerror694、出反馈模式OFBOFB模式实际上就是一个同步流密码，通过反复加密一个初始向量IV来产生一个密钥流，将此密钥流和明文流进行异或可得密文流。仍然需要一个初始向量（IV）。IV应当唯一但不须保密。加密和解密可表示为：加密：S0=IV；Si=Ek（Si-1）；Ci=Pi⊕Si解密：Pi=Ci⊕Si；Si=Ek（Si-1）70（5）计数模式CTR该模式使用一个计数ctr（也是一个初始向量）。如图3-17所示。加密：Ci=Ek（ctr+i）⊕Pi解密：Pi=Ek（ctr+i）⊕Ci71Counter(CTR)723.4非对称密码体制

RSAandDiffie-HellmanRSA-RonRives,AdiShamirandLenAdlemanatMIT,in1977.RSAisablockcipherThemostwidelyimplementedDiffie-Hellman

EchangeasecretkeysecurelyComputediscretelogarithms(离散对数)

73RSAAlgorithm概述

1977年，Rivest、Shamir、Adleman提出的非对称密码体制，是基于大合数的质因子分解问题的困难性。目前人类已能分解十进制150位的特殊类型的大合数第9个费马数，1994年4月一个小组通过Internet合作，8个月时间成功分解129位的数，大约428比特，最新的记录是1996年分解130位合数。RSA专利于2000年9月20日到期。743.4.1RSARSA算法的思路如下：为了产生两个密钥，先取两个大素数，p和q。为了获得最大程度的安全性，两数的长度一样。计算乘积n=p*q，然后随机选取加密密钥e，使e和（p-1）*（q-1）互素。最后用欧几里得（Euclidean）扩展算法计算解密密钥d，d满足ed≡1mod（p-1）（q-1），即d≡e-1mod（p-1）（q-1）。则e和n为公开密钥，d是私人密钥。两个大数p和q75算法流程随机选择两个秘密大质数p和q；计算公开模数n=p*q；计算秘密的欧拉指数函数φ(n)=(p-1)(q-1)选择一个与φ(n)互素的数K，作为e或d；用Euclid算法计算模φ(n)的K的乘法逆元素，即依edmodφ(n)=1,求d或e；加密：C=Memodn解密：M=Cdmodn=(Memodn)dmodn=M

这里，φ(n)为EulerTotientFunction，欧拉商数，即模n的完全剩余集合(0,1,2,...,n-1)中与n互素的数的个数。76加密消息时，首先将消息分成比n小的数据分组（采用二进制数，选到小于n的2的最大次幂），设mi表示消息分组，ci表示加密后的密文，它与mi具有相同的长度。加密过程：ci=mie（modn）解密过程：mi=cid（modn）77TheRSAAlgorithm-Encryption

Plaintext: M<nCiphertext: C=Me(modn)78TheRSAAlgorithm-Decryption

Ciphertext: CPlaintext: M=Cd

(modn)79RSA算法满足公开密钥加密的要求，必须符合下列条件有可能找到e,d,n的值，使得对所有M<n有

Medmodn=M对于所有M<n的值，要计算Me和Cd是相对容易的在给定e和n时，计算出d是不可行的几个关系φ(n)=φ(pq)=φ(p)φ(q)=(p-1)(q-1),p,qareprimeedmodφ(n)=1,ed=kφ(n)+1,即ed≡1modφ(n),d≡e-1modφ(n)80一个实际的例子来帮助理解RSA算法。①选择素数:p=17&q=11②计算n=pq

=17×11=187③计算ø（n）=（p–1）（q-1）=16×10=160④选择e:gcd（e,160）=1;选择e=7⑤确定d:de=1mod160且d<160，d=23因为23×7=161=1×160+1⑥公钥KU={7,187}⑦私钥KR={23,187}假设给定的消息为：M=88，则•加密:C=887mod187=11•解密:M=1123mod187=8881DiscreteLogarithmProblem(DLP)离散对数问题DiscreteLogarithmProblem(DLP)

如果a是素数p的一个原根(本原元素)，则amodp,a2modp,......,ap-1modp，生成模p的完全剩余集{1,2,......,p-1}对于所有素数，其原根必定存在，即对于一个整数b和素数p的一个原根，可以找到唯一的指数i，使得b=aimodp其中0<=i<=p-1指数i称为b的以a为基数的模p的离散对数或者指数。给定整数x，求y=axmodp容易；若给定p,a及y，求x，则为DLP问题，最快方法需要L(p)=exp{(lnpln(lnp))½}次运算。3.4.2Diffie—Hellman算法82例：p=11,a=2,<Ex(a)>={20,21,22,…,210}={1,2,4,8,5,10,9,7,3,6,1}

即：20=1mod11 26=9mod11 21=2mod11 27=7mod11 22=4mod11 28=3mod11 23=8mod11 29=6mod11 24=5mod11 210=1mod1125=10mod11给定整数x，求y=axmodp,最多需要[log2x]+w(x)-1次乘法，w(x)为x中所有1的个数。如x

=15，即x

=(1111)2，w(x)=4，则a15=((a2)a)2·a)2·amodp，只需要3+4-1=6次乘法。但是若给定p,a及y，求x，则为DLP问题。最快方法需要L(p)=exp{(lnpln(lnp))½}次运算。当p=512位时，L(p)约为2256≈1077，计算上不可行。因为2100≈1030，计算要1016年。83Diffie-HellmanSetupAllusersagreeonglobalparameters:largeprimeintegerorpolynomialqαaprimitiverootmodqEachuser(e.g.A)generatestheirkeychoosesasecretkey(number):xA<qcomputetheirpublickey:yA=αxAmodqEachusermakespublicthatkeyyA84Diffie-HellmanKeyExchangeSharedsessionkeyforusersA&BisKAB:KAB=αxA.xBmodq=yAxBmodq(whichBcancompute)=yBxAmodq(whichAcancompute)KABisusedassessionkeyinprivate-keyencryptionschemebetweenAlic