Sarah Flannery的十六歲小女孩發明了Cayley-Purser這種密碼

發文回覆瀏覽次數：6087

推到 Plurk!

推到 Facebook!

Sarah Flannery的十六歲小女孩發明了Cayley-Purser這種密碼

jackkcg
站務副站長

發表：891
回覆：1050
積分：848
註冊：2002-03-23

發送簡訊給我

#1 引用回覆回覆

發表時間：2002-09-29 15:05:41

IP:61.70.xxx.xxx 未訂閱

發信人: cschang@bbs.ee.ntu.edu.tw (我怕貓!), 信區: Linux 標題: [News] 十六歲女孩發明新密碼演算法發信站: 台大電機 Maxwell BBS (Wed Jan 13 23:13:36 1999) 轉信站: cmc!news.cmc!ccnews.nchu!ctu-gate!news.nctu!news.ntu!bbs.ee.ntu!Maxwell 來自BBC的消息, http://news.bbc.co.uk/hi/english/sci/tech/newsid_254000/254236.stm 一個名叫Sarah Flannery的十六歲小女孩發明了Cayley-Purser這種密碼, 並可證明至少跟RSA一樣安全, 不同的是, RSA將一篇文章編碼需時30分鐘, Cayley-Purser 碼卻只要1分鐘. 更好的是, 這位慷慨的Flannery小姐打算把這種編碼法送給大家自由使用.... (原文如下) Making your email secret is now 30 times faster, but the innovation has come not from a multinational computer computer but a schoolgirl from Blarney, Ireland. Sarah Flannery, 16, has developed a brand new mathematical procedure for encrypting internet communication. "The algorithm is based on matrices," her father told BBC News Online. Dr David Flannery is a mathematics lecturer at Cork Institute of Technology, Ireland. "Sarah has a very good understanding of the mathematical principles involved, but to call her a genius or a prodigy is overstated and she doesn't want that herself. Encryption technology codes internet messages to keep email and online commerce secure"She's a normal young girl, who likes basketball and going out with her friends." International job offers But her number-crunching feat is undoubtedly remarkable and won her the top prize at the Irish Young Scientists and Technology Exhibition. International job and scholarship offers have flooded in, said Dr Flannery. Last year, Ms Flannery's cryptography skill took her to Fort Worth, Texas, as the winner of an Intel prize. Even when high security levels are required, her code can encrypt a letter in just one minute - a widely used encryption standard called RSA would take 30 minutes. "But she has also proven that her code is as secure as RSA," says Dr Flannery. "It wouldn't be worth a hat of straw if it was not." Ms Flannery currently has a bad cold and has not had time to consider the advice of the judges to patent the code. "She wouldn't mind being rich but she wants to stress the great joy that the project has given her," says Dr Flannery. She may publish the work to make it freely available to all. Her code is called Cayley-Purser after Arthur Cayley, a 19th century Cambridge expert on matrices, and Michael Purser, a cryptographer from Trinity College, Dublin, who provided inspiration for Ms Flannery. -- ※ Origin: 臺大電機 Maxwell 站 ◆ From: pc5336.ee.ntu.edu.tw -------------------------------------------------------------------------------- 參考網址 http://www.inet-one.com/cypherpunks/dir.1999.03.15-1999.03.21/msg00092.html ********************************************************************** http://cryptome.org/flannery-cp.htm <HTML> <HEAD> <META HTTP-EQUIV="content-type" CONTENT="text/html;charset=iso-8859-1"> <META NAME="generator" CONTENT="GoLive CyberStudio">  <TITLE>Sarah Flannery on Cayley-Purser: An Investigation of a New Algorithm vs. the RSA</TITLE> </HEAD> <BODY BGCOLOR="#FFFFFF"> 12 June 2000: Add link to Sarah Flannery's Web site with the original of her Cayley-Purser paper. Thanks to J-JQ. 22 November 1999: Sarah Flannery writes today the good news that she will put her paper online soon, free of any errors which may remain in this version. URL when it's available. 17 November 1999. Many thanks to Erick Wong for countless(!) typos corrected. Add William Whyte message on the successful attack on Cayley-Purser. 13 November 1999. Add transcription of Mathematica code of the RSA and C-P algorithms, which completes the HTML conversion of the full document. 12 November 1999: Add transcriptions of "The Cayley-Purser Algorithm," "Wherein lies the security of the Cayley-Purser Algorithm?," "Empirical Run-time Analysis," Post Script attack and Bibliography. Joe Author provided a PDF version of the 18 TIF images in a smaller package: http://cryptome.org/flannery-cp.pdf (603KB). 11 November 1999
Source: TIF images provided by Jean-Jacques Quisquater of 18-page hardcopy provided by Jean-François Misarsky. Set of 18 images http://cryptome.org/flannery-cp.zip (1.2MB) See press release: http://europa.eu.int/comm/dg12/press/1999/pr2509en.html See related January 1999 report: http://jya.com/flannery.htm In equations single letters are substituted for Greek characters. Double check all equations with original images. Errata welcome; send to jy@jya.com [Document undated; apparently September 1999. Excerpts.]

Cryptography:
An Investigation of a New Algorithm vs. the RSA

Sarah Flannery, Blarney, Co. Cork, Ireland

Introduction

The RSA Algorithm

The Cayley-Purser Algorithm

Wherein lies the security of the Cayley-Purser Algorithm?

Some differences between the RSA and Cayley-Purser Algorithms

RSA vs. Cayley-Purser -- Empirical Time Analysis

Graph: CP vs. RSA -- Comparison of Enciphering Times

Conclusions

Post Script: An Attack on the CP Algorithm

Appendix of Programmes

-- Mathematica Code for RSA Algorithm
-- Mathematica Code for Cayley-Purser Algorithm

Bibliography

Cryptography:

An Investigation of a New Algorithm vs. the RSA

Introduction As long as there are creatures endowed with language there will be the desire for confidential communication -- messages intended for a limited audience. Governments, companies and individuals have a need to send or store information in such a way that on the intended recipient is able to read it. Generals send orders, banks send fund transfers and individuals make purchases using credit cards. Cryptography is the study of methods to 'disguise' information so that only the intended receipient can obtain knowledge of its content. Public-Key Cryptography was first suggested in 1976 by Diffie and Hellman and a public-key cryptosystem is one which has the property that someone who knows only how [to] encipher ('disguise') a piece of information CANNOT use the enciphering key to find the deciphering key without a prohibitively lengthy computation. This means that the information necessary to send private or secret messages, the enciphering algorithm along with the enciphering key, can be made public-knowledge by submitting them to a public directory. The first public-key cryptosystem, the RSA Algorithm, was developed by Ronald Rivest, Adi Shamir and Leonard Adleman at MIT in 1977. This system, described below, has stood the test of time and is today recognised as a standard of encryption worldwide. Aim This project investigates a possible new public-key algorithm, entitled the Cayley-Purser (CP) Algorithm and compares it to the celebrated RSA public-key algorithm. It is hoped that the CP Algorithm is

As secure as the RSA Algorithm and

FASTER than the RSA Algorithm

Firstly both algorithms are presented and why they both work is illustrated. A mathematical investigation into the security of the Cayley-Purser algorithm is discussed in the main body of the report. Some differences between the RSA and the CP algorithms are then set out. Both algorithms are programmed using the mathematical package Mathematica and the results of an empirical run-time analysis are presented to illustrate the relative speed of the CP Algorithm.

RSA Public Key Cryptosystem

The RSA scheme works as follows: Start Up: [This need be done only once.]

Generate at random two prime numbers p and q of 100 digits or more.

Calculate n = pq phi(n) = (p-1)(q-1) = n - (p q) 1.

Generate at random a number e < phi(n) such that (e, phi(n)) = 1.

Calculate the multiplicative inverse, d, of e (mod phi(n)) using the Euclidean algorithm.

Publish: Make public the enciphering key, K_E = (n, e) Keep Secret: Conceal the deciphering key, K_D = (n, d) Enciphering: The enciphering transformation is, C = f(P) = P^e (mod n) Deciphering: The deciphering transformation is, P = f^--1(C) = C^d (mod n) Why the deciphering works:- The correctness of the deciphering algorithm is based on the following result due to Euler, which is a generalization of what is known as Fermat's little theorem. This result states that, a^phi⁽ⁿ⁾ = 1 (mod n) whenever (a, n) = 1, where phi(n), Euler's-phi function, is the number of positive integers less than n which are relatively prime to n. When n = p, a prime, phi(n) = p - 1, and we have Fermat's theorem: a^p^-1 = 1 (mod p) ; (a, p) = 1 If p|a then a^p = a = 0 (mod p), so that for any a, a^p = a (mod p) Now since d is the multiplicative inverse of e, we have ed = 1 (mod phi(n)) => ed = 1 k phi(n), k in Z Now f^--1(f(P)) = (P^e)^d = P^ed (mod n) and P^ed = P^{1 k
phi(n)} (mod n) (for some integer k) Now for P with (P, p) = 1, we have P^p^-1 = 1 (mod p) => P^{k
phi}^{(n) 1} = P (mod p) as p - 1|phi(n) This is trivially true when P = 0 (mod p), so that for all P, we have P^ed = P^{1 k
phi(n)} = P (mod p) Arguing similarly for q, we have for all P, P^ed = P^{1 k
phi(n)} = P (mod q) Since p and q are relatively prime, together these equations imply that for all P, P^ed = P^{1 k
phi(n)} = P (mod n).

The Cayley-Purser Algorithm

Introduction Since this algorithm uses 2 x 2 matrices and ideas due to Purser it is called the Cayley-Purser Algorithm. The matrices used are chosen from the multiplicative group G = GL(2, Z_n). The modulus n = pq, where p and q are both primes of 100 digits or more, is made public along with certain other parameters which will be described presently. Since |GL(2, Z_n)| = n phi(n)²(p 1)(q 1) we note that the order of G cannot be determined from a knowledge of n alone. Plaintext message blocks are assigned numerical equivalents as in the RSA and placed four at a time in the four positions (ordered on the first index) of a 2 x 2 matrix. This message matrix is then transformed into a cipher matrix by the algorithm and the corresponding ciphertext is then extracted by reversing the assignment procedures used in the encipherment. Because this algorithm uses nothing more than matrix multiplication (modulo n) and not modular exponentiation as required by the RSA it might be expected to encipher and decipher considerably faster than the RSA. This question was investigated, using the mathematical package Mathematica, by applying both algorithms to large bodies of text (see Tables I-IX) and it was found that the Cayley-Purser algorithm was approximately twenty-two times faster than the RSA with respect to a 200-digit modulus. Needless to say if it could be shown that this algorithm is as secure as the RSA then it would recommend itself on speed grounds alone. The question of security of this algorithm is discussed after we have described it and explained why it works.

The CP Algorithm

Start Up: procedure to be followed by B (the receiver): [Cryptome note: Here "in" is used for the element inclusion symbol.]

Generate two large primes p and q.

Calculate the modulus n = pq.

Determine x and a in GL(2, Z_n) such that xa^-1 /= ax.

Calculate b = x^-1a^-1x.

Calculate g = x^r ; r in N.

Publish: The modulus n and the parameters a, b, and g Start Up Procedure to be followed by A (the sender): In order to encipher the matrix µ corresponding to a plaintext unit for sending to B, Person A must consult the parameters made public by B and do the following:

Generate a random t in N

Calculate s = g^t

Calculate e = s^-1as

Calculate k = s^-1bs

Enciphering Procedure When the above parameters are calculated, A enciphers µ via µ' = kµk and sends µ' and e to B Deciphering Procedure When A receives µ' and e (s)he does the following: Calculates l = x^-1ex and deciphers µ' via µ = lµ'l Why the deciphering works. The deciphering works since

l = x^-1ex = x^-1(s^-1as)x = s^-1(x^-1ax)s : (s. being a power of x. commutes with x) = s^-1(x^-1a^-1x)^-1s = s^-1b^-1s : (recall that b = x^-1a^-1x) = (s^-1bs)^-1 = k^-1 : ( B's enciphering key )

so that lµ'l = l(k µ k)l = (k^-1k)µ(kk^-1) = µ.

Wherein lies the security of the Cayley-Purser Algorithm?

To find the secret matrix x, known to B alone, one might attempt to solve either the equation b = x^-1a^-1x or g = x^r In the first of these equations the matrix b is public and the matrix a^-1 can be computed since both the matrix a and the modulus n are public. In the second equation only the matrix g is known and it is required to solve for both the exponent r and the base matrix x. Assuming that one knew r, solving this equation would involve extracting the r^th - roots of a matrix modulo the composite integer n. Even in the simplest case, where r = 2, extracting the square root of a 2 x 2 matrix modulo n requires that one be able to solve the ordinary quadratic conruence [as written] x² = a (mod n) when n = pq. It is known that the ability to solve this 'square root' problem is equivalent to being able to factor n. Thus we may regard an attack on x via the public parameter g as being computationally prohibitive. Solving the equation b = x^-1a^-1x would appear the easier option for an attack on the private matrix x as it only involves solving the set of linear equations given by xb = a^-1x However the number of possible solutions to this equation is given by the order of C(a), the centraliser of a in GL(2, Z_n). By ensuring that the order of this group is extremely large one can make it computationally prohibitive to search for x. To see why this is the case suppose that b = x^-1a^-1x and b = x₁^-1a^-1x₁ Then x^-1a^-1x = x₁^-1a^-1x₁ If and only if a^-1xx₁^-1 = xx₁^-1a^-1 If and only if xx₁^-1 in C(a^-1) If and only if x in C(a^-1)x₁ Thus the number of distinct solutions of the equation is given by |C(a)| as C(a^-1) = C(a). Now C(a) will have a large order if the matrix element a has a large order. By choosing our primes p and q to be of the form p = 2p¹ 1 and q = 2q¹ 1, where p¹ and q¹ are themselves prime, we can show that it is almost certainly the case that an element a chosen at random from GL(2, Z_n) has a large order. To see why, we begin by considering the homomorphism p of GL(2, Z_n) onto Z_n defined by sending a matrix into its determinant. The order of a matrix in GL(2, Z_n) is at least that of the order of its image in Z_n since ... If r is the order of A in GL(2, Z_n) and p(A) = u then A^r = I with 1 = p(I) = p(A^r) = p(A)^r = u^r shows that m divides r where m is the order of u in Z_n. Thus the order of A in GL(2, Z_n) is at least m. In fact p(A^m) = p(A)^m = u^m = 1 shows that A^m lies in SL (2, Z_n) so the matrix A will have order µ iff A^m = I in SL (2, Z_n). We note also that since the maximum achievable order of an element in Z_n is

[p - 1, q - 1]	<	(p - 1)(q - 1) __________	=	phi(n) ___
		2		2

(as (p - 1, q - 1) > 2) and since the order of SL (2, Z_n) is n phi(n)(p 1)(q 1) the maximum achievable order of a matrix in GL(2, Z_n) is [p - 1, q - 1] n phi(n)(p 1)(q 1) < n phi(n)²(p 1)(q 1)/2 = |GL(2, Z_n)|/2. Thus if we can show that the probability of an element having a small order in Z_n is negligibly small then we will have shown that the order of an element chosen at random from GL(2, Z_n) is almost certainly of 'high order.' If p = 2p¹ 1 and q = 2q¹ 1 then phi(n) = phi(pq) = (p - 1)(q - 1) = 2p¹2q¹ = 4p¹q¹ with [p - 1, q - 1] = [2p¹ · 2q¹ ] = 2p¹q¹ = phi(n)/2 Now the possible orders of the elements in Z_n are divisors of phi(n)/2 = 2p¹q¹ and so are 1, 2, p¹ · q¹ · 2p¹, 2q¹ · p¹q¹ · 2p¹q¹ and all of these orders are achieved by some elements. In fact by counting exactly how many elements correspond to each order we show that the probability of finding a unit in Z_n of order less than p¹q¹ is negligibly small. Recall that if a in Z_p has order k and b in Z_q has order l then the order of c in Z_n where c = a (mod p) and c = b (mod q) is [k, l], the least common multiple of k and l. Now the possible orders of a and b in Z_p and Z_q are divisors of p - 1 = 2p¹ ; q - 1 = 2q¹ respectively. The following table lists the possible orders along with the number of elements of each order.

Z^*_p		Z^*_q
Possible Orders	No. of elements of that order	Possible Orders	No. of elements of that order
1	1	1	1
2	1	2	1
p¹	p¹ - 1	q¹	q¹ - 1
2p¹	p¹ - 1	2q¹	q¹ - 1

By lifting elements in pairs via the CRT we obtain the elements corresponding to the different orders in Z_n along with number of elements of each order.

Order	Number	Reason
1	1	[1, 1] = 1
2	3	[1, 2] = [2, 1] = [2, 2] = 2
p¹	p¹ - 1	[p¹, 1] = p¹
q¹	q¹ - 1	[1, q¹] = q¹
2p¹	3p¹ - 3	[2p¹, 1] = [p¹, 2] = [2p¹, 2] = 2p¹
2q¹	3q¹ - 3	[1, 2q¹] = [2, q¹] = [2, 2q¹] = 2q¹
p¹q¹	p¹q¹ - p¹ - q¹ 1	[p¹, q¹] = p¹q¹
2p¹q¹	3p¹q¹ - 3p¹- 3q¹ 3	[2p¹, q¹] = [p¹, 2q¹] = [2p¹, 2q¹] = 2p¹q¹

Note that if we sum all the individual counts we get exactly 4p¹q¹ which is the number of elements of Z_n. Explanation: To see how the number of elements corresponding to an order is obtained consider the last entry in the above array: An element of order 2p¹q¹ in Z_n can be obtained in 3 different ways by lifting pairs of elements from Z_p and Z_q: One way is lifting the pair (a, b) where a has an order 2p¹ and b has order q¹; another by lifting the pair (a, b) where a has an order p¹ and b has order 2q¹ and another by lifting the pair (a, b) where a has an order 2p¹ and b has order 2q¹. Regarding elements of order less than p¹q¹ as elements of 'low order' we obtain the probability of choosing an element of order less than p¹q¹ to be

4p¹ 4q¹- 4 ___________

4p¹q¹

This is equivalent to 1/p¹ 1/q¹ - 1/p¹q¹ In the case where p and q are both of order of magnitude 10¹⁰⁰ this probability is approximately 2.10^-100 which, by any standards, is negligibly small.

Some differences between the RSA and Cayley-Purser Algorithms
------
**********************************************************
哈哈&兵燹
最會的2大絕招這個不會與那個也不會哈哈哈粉好

Delphi K.Top的K.Top分兩個字解釋Top代表尖端的意思,希望本討論區能提供Delphi的尖端新知
K.表Knowlege 知識,就是本站的標語:Open our mind

kynix
初階會員

發表：37
回覆：100
積分：37
註冊：2002-06-01

發送簡訊給我

#2 引用回覆回覆

發表時間：2002-09-29 18:20:01

IP:61.225.xxx.xxx 未訂閱

最近出現了很多超聰明的天才,我看我們要注意了^^ 智慧是命運的征服者

------
智慧是命運的征服者

jackkcg
站務副站長

發表：891
回覆：1050
積分：848
註冊：2002-03-23

發送簡訊給我

#3 引用回覆回覆

發表時間：2002-09-29 20:25:58

IP:61.70.xxx.xxx 未訂閱

這是數年前的資料了連結上好巷有書介紹它比你大賣反樂啦哈哈

------
**********************************************************
哈哈&兵燹
最會的2大絕招這個不會與那個也不會哈哈哈粉好

Delphi K.Top的K.Top分兩個字解釋Top代表尖端的意思,希望本討論區能提供Delphi的尖端新知
K.表Knowlege 知識,就是本站的標語:Open our mind

AB
高階會員

發表：166
回覆：262
積分：125
註冊：2003-08-21

發送簡訊給我

#4 引用回覆回覆

發表時間：2003-12-10 02:33:51

IP:61.64.xxx.xxx 未訂閱

http://www.vtsh.tc.edu.tw/~jck/sci-math/encryption.htm 三更有夢書當枕

前天(2000/1/25)凌晨,在半夢半醒之間想到一個問題: 我把班上01~55號每個人的座號除以n,取小數點後之4位數作password,則若n=7,則顯然有許多人password重號若n=37,大概每個人皆不重號(容易證明嗎?) 若n未知,有沒有辦法知道,例如1372座號是幾號? 給幾個數據,可以知道n=? 如果給的不是座號,而是英文字母,則可以視為26進位數,情形如何? ... 早上,我把這樣的想法告訴老賴,10點多,我跑到瀋陽北路剪頭髮,隨手看看雜誌,看到一篇"加密編碼技術"的報導. 故事是說,一年多以前(1999年),有一個叫作Sarah Flannery 的愛爾蘭少女發明了稱為"Cayley-Purser"的加密編碼技術.[註1]目前使用最廣泛的加密技術叫RSA編碼技術,是由麻省理工學院的一群電腦專家所研製,該雜誌如是說.[註2] 加密編碼技術是電子商務的重要技術,而加密演算法(encryption algorithm)要用到研究所以上的數學.Sarah的父親David Flannery是Cork理工學院的數學教授,Sarah上了他父親所授的課程就對編碼學有興趣,然後在巴爾的摩科技公司打雜,Michael Purser建議她花些時間把可能比RSA[註3]更有效率的演算法做出來.Sarah成功了,而且把她的發明放在網路上,供網友免費取用,她說:身為一個科學家,應該把好的構想與他人分享,申請專利只會妨礙這樣的過程. -------------------------------------------------------------------------------- 我的夢和加密技術當然關係不大,但是可能可以發展成一個科展的好題目喔! -------------------------------------------------------------------------------- 幹嘛學數學(Strength in Numbers by Sherman K. Stein) 談談數論和它的應用(二十一世紀雜誌 1991/12 p.87 王元)----裡面有trapdoor function較詳細的說明一千零一網 p.185 [註1]:Sarah的加密技術叫作Cayley-Purser 演算法,是為了紀念19世紀的數學家Arthur Cayley,他是矩陣專家;以及給她原始構想的巴爾的摩科技公司(Baltimore Technologies)的創始人Michael Purser [註2]該技術是1977年由三個數學家Ronald Rivest,Adi Shamir,Leonard Adleman利用數論發明的一種密碼,後來三人還成立了"RSA數據保全公司". [註3]Cayley-Purser與 RSA都是針對公約密碼學 ("public-key" cryptography)而設計, . 使用叫作"活板門函數(trapdoor function)的觀念,使得一個方向的計算很容易,但是另一個方向的計算很難.因此很難破解.例如,你很容易把兩個很大的質數相乘,但是要別人反過來分解卻很難. http://www.rsasecurity.com/

發表人 - ab 於 2003/12/10 02:35:18

cmf
尊榮會員

發表：84
回覆：918
積分：1032
註冊：2002-06-26

發送簡訊給我

#5 引用回覆回覆

發表時間：2003-12-10 09:25:04

IP:61.218.xxx.xxx 未訂閱

J SIR 最近在忙什麼好久沒看到你了ㄋㄟ ^_^ 每天省下一包菸的錢愛心1000元餵飽一名非洲飢餓兒童 http://www.worldvision.org.tw/edm/30hffan/30hf1000.htm

------
︿︿

系統時間：2024-05-03 0:34:19

聯絡我們 | Delphi K.Top討論版

本站聲明

1. 本論壇為無營利行為之開放平台，所有文章都是由網友自行張貼，如牽涉到法律糾紛一切與本站無關。
2. 假如網友發表之內容涉及侵權，而損及您的利益，請立即通知版主刪除。
3. 請勿批評中華民國元首及政府或批評各政黨，是藍是綠本站無權干涉，但這裡不是政治性論壇！

Sarah Flannery的十六歲小女孩發明了Cayley-Purser這種密碼

Cryptography: An Investigation of a New Algorithm vs. the RSA

Contents

Cryptography:

An Investigation of a New Algorithm vs. the RSA

RSA Public Key Cryptosystem

The Cayley-Purser Algorithm

The CP Algorithm

Wherein lies the security of the Cayley-Purser Algorithm?

Cryptography:
An Investigation of a New Algorithm vs. the RSA