پایان نامه مقایسه چهار طرح ضرب کننده RNS

پایان نامه مقطع کارشناسی ارشد

رشته معماری کامپیوتر

سال 1385

- مقدمه

همانطور كه مي دانيم ضرب پيمانه اي در علم رمزنگاري نقش مهمي ايفا مي كند. از جمله روشهاي رمزنگاري كه به ضرب كننده پيمانه اي سريع نياز دارد، روش رمزنگاري RSA مي باشد كه در آن نياز به توان رساندن اعداد بزرگ در پيمانه هاي بزرگ مي باشد. معمولاً براي نمايش اعداد در اين حالات از سيستم باقي مانده (RNS) استفاده مي شود و ضرب (به عنوان هسته توان رساني) در اين سيستم به كار مي رود.

در اينجا براي آشنايي بيشتر به توضيح سيستم عددي باقي مانده مي پردازيم و به كاربردها و فوايد آن اشاراتي خواهيم داشت.

1-1 سيستم عددي باقيمانده (Residue Number System (RNS))

در حدود 1500 سال پيش معمايي به صورت شعر توسط يك شاعر چيني به صورت زير بيان شد. «آن چه عددي است كه وقتي بر اعداد 3،5و7 تقسيم مي شود باقيمانده هاي 2،3و2 بدست مي آيد؟» اين معما يكي از قديمي ترين نمونه هاي سيستم عددي باقي مانده است.

در RNS يك عدد توسط ليستي از باقيمانده هايش برn  عدد صحيح مثبت m1 تا mn كه اين اعداد دو به دو نسبت به هم اولند (يعني بزرگترين مقسوم عليه مشترك دوبدوشان يك است) به نمايش در مي آيد. به اعداد m1 تا mn پيمانه (moduli)
مي گويند. حاصلضرب اين nعدد،  تعداد اعدادي كه مي توان با اين پيمانه ها نشان داد را بيان مي كند. هر باقيمانده xi را به صورت xi=Xmod mi نمايش مي دهند. در مثال بالا عدد مربوطه به صورت X=(2/3/2)RNS(7/5/3) به نمايش در مي آيد كه X mod7=2 و X mod5=3 و X mod3=2. تعداد اعداد قابل نمايش در اين مثال  مي باشد. مي توان هرمجموعه 105 تايي از اعداد صحيح مثبت يا منفي متوالي را با اين سيستم عددي باقيمانده نمايش داد.

اثبات اين كه هر عدد صحيح موجود در محدوده، نمايش منحصر به فردي در اين سيستم دارد به كمك قضيه باقي‌مانده هاي چيني(Chinese Remainder Theorem (CRT)) امكان پذير است. اين قضيه به صورت زير بيان مي شود:

1-2 قضيه باقي مانده هاي چيني:

اعداد صحيح مثبت  را كه نسبت به هم دو به دو اول هستند در نظر بگيريد و M را حاصلضرب  فرض كنيد. همچنين اعداد  را فرض كنيد. اثبات مي شود كه فقط و فقط يك عدد صحيح U وجود دارد كه شرايط زير دارد:

    ,         ,    

كه U برابر است با:

اعمال رياضي جمع، تفريق و ضرب به راحتي و به صورت زير در اين سيستم انجام مي شود.

   ,  

در فرمول بالا به جاي علامت مي توان هر كدام از علائم +،-،* را قرار داد.

سه عمل رياضي (+،-،*) در اين سيستم عددي راحت‌تر از سيستم نمايش عادي اعداد انجام مي شود، زيرا هنگام انجام اين عمل در اين سيستم رقم نقلي (carry) بين بخشها رد و بدل نمي شود. در واقع انجام عمليات مربوط به مانده هاي هر پيمانه تاثيري روي ديگر عمل ها ندارد. يعني محاسبه “” مي تواند بطور مستقل (و در واقع موازي) انجام شود و نتيجه آن تاثيري در بقيه “”ها ندارد. بدين ترتيب عمليات رياضي سريعتر (بعلت موازي شدن) و راحت تر (بعلت عدم تاثيرگذاري محاسبات مربوط به هر مانده برهم) انجام مي شود.

1-3- كاربردهاي RNS

سيستم عددي باقي مانده در چند دهه اخير مورد توجه قرار گرفته، زيرا مي توان بعضي از اعمال رياضي را تحت RNS به صورت چند مجموعه زير عمل رياضي تقسيم كرد. ولي به دليل اينكه اين اعمال فقط شامل ضرب، جمع و تفريق هستند از RNS در محاسبات “خاص منظوره” استفاده مي شود. RNS در پياده سازي سريع مسائلي كه شامل تصحيح و تشخيص خطا در سيستم هاي Fault-tolerant و سيستم‌هاي پردازش سيگنال هستند كاربرد دارد. كاربردهايي از قبيل تبديل فوريه سريع، فيلتر ديجيتال و پردازش تصوير از اعمال رياضي سريع RNS استفاده مي كند. RNS راه خود را در كاربردهايي مثل تبديلات تئوري اعداد و تبديل فوريه گسسته پيدا كرده است. همچنين مستقل بودن رقم هاي باقيمانده باعث مي شود كه رخ دادن خطا در يك رقم به رقم هاي بعدي منتقل نشوند كه اين مسأله، باعث ايجاد يك معماري Fault-tolerant خواهد شد. [35],[20]

سيستم عددي RNS در رمزنگاري و به خصوص در روش RSA كاربرد زيادي دارد[35]. البته در RSA از ضرب پيمانه اي جهت عمليات توان رساني استفاده مي‌شود.

در اين پروژه سعي مي شود كه چهار طرح از رويكردهاي ضرب RNS را پياده‌سازي و با هم مورد مقايسه قرار دهيم. اين مقايسه براساس حجم و تاخير طرح ها مي‌باشد. در پياده سازي سعي شده است كه از پيشنهادات مقالات جهت عناصر بكار رفته استفاده شود (بخصوص در دو طرح اول) و در مواقعي كه پيشنهاد خاصي انجام نشده (مثل طرح هاي سوم و چهارم) پيشنهاد مناسب از لحاظ خود من انجام شده است.

در ادامه ابتدا به اصول ضرب RNS و روشهاي بكار رفته براي اينكار اشاره مي‌كنيم. سپس هر يك از چهار طرح را به تفصيل مورد بررسي قرار مي دهيم و در مورد هر طرح، الگوريتم و سخت افزار بيان خواهد شد و سپس تاخير و مساحت آن را تعيين مي كنيم. در نهايت جمع بندي و مقايسه چهار طرح را انجام مي دهيم. در ضمايم نيز كدهاي VHDL نوشته شده را خواهيد يافت.

2- روشهاي ضرب پيمانه اي

اين روشها را مي توان به دو دسته كلي تقسيم كرد. در دسته اول ابتدا عمل ضرب به صورت كامل انجام مي شود و سپس كاهش به پيمانه روي نتيجه آخر اعمال مي شود. اين روشها را Reduction After Multiplication (RAM) مي نامند. در دسته دوم عمل كاهش به پيمانه در هر مرحله ضرب و با هر حاصلضرب جزئي انجام مي شود كه به اين روشها Reduction During Multiplication (RDM) مي گويند[38]. از ميان طرحهاي مورد نظر ما دو طرح اول به دسته اول و دو طرح بعدي به دسته دوم تعلق دارند.

2-1- روش مونتگمري

در روش RDM چون روش كاهش به پيمانه به دفعات تكرار مي شود بايد اين عمل را سرعت بخشيد. يكي از تكنيك هاي پر طرفدار براي اينكار كه در طرحهاي ما نيز به كار رفته روش مونتگمري [2] در كاهش پيمانه است.

پيمانه N را در نظر بگيريد. عدد R را كه نسبت به N اول است و N

function REDC(T):

if

بدين ترتيب با به كارگيري عدد كمكي R، عمل كاهش T به پيمانه N سريعتر انجام مي شود.

2-2- بررسي اجمالي روشهاي موجود پياده سازي ضرب در RNS

طرحهاي ارائه شده را مي توان براساس روش پياده سازي سخت افزاري به سه مجموعه تقسيم كرد.

مجموعه اول:

از تعداد خاصي از پيمانه ها مثل  استفاده مي كنند. در اين مجموعه n مي تواند مقادير كوچك، متوسط و گاهي بزرگ داشته باشد. در پياده سازي اين طرح ها عمدتاً فقط از مدارات منطقي استفاده شده و از ROM استفاده نمي شود. در هر حال اين طرحها به پيمانه هاي خاصي محدود هستند و به همين دليل كاربردهاي محدودي دارند[3]. به طور مثال مي توان به طرحهاي [13],[12],[11] مراجعه كرد.

مجموعه دوم:

توانايي كار با هر پيمانه اي را دارند ولي پياده سازي اين گروه، راه حلهايي بر اساس ROM دارند و معمولاً از مدارات منطقي ديگر استفاده چنداني نمي كند. اندازه حافظه با افزايش n به سرعت رشد مي كند كه طرح را براي پيمانه‌اي بزرگ غير عملي مي سازد. به طور مثال مي توان طرحهاي [10],[9],[8],[7] را ذكر كرد.

مجموعه سوم:

جهت پيمانه هاي متوسط و بزرگ طراحي مي شوند. معمولاً به صورت هيبريد هستند و از عناصر رياضي پايه مثل ضرب و جمع كننده هاي باينري كه به صورت موازي عمل مي كنند به همراه چندين ROM با اندازه كوچك و عناصري منطقي استفاده مي كند. طرحهاي مورد نظر ما در اين دسته قرار مي گيرند. همچنين مي توان به طرحهاي [18],[17],[16],[15],[14] اشاره كرد.

2-3- نكاتي پيرامون چهار طرح موردنظر

اين طرحها از مقالات [6],[5],[4],[3] انتخاب شده اند. دو طرح با تكنيك RAM كار مي كنند و از تكنيك هاي ابتكاري سود مي جويند و امكان پياده سازي دقيق و در سطح گيت آنها وجود دارد. دو طرح بعدي با هدف بهبود الگوريتم رمزنگاري RSA انتشار يافته اند و طرحهاي ضرب براي RNS به روش RDM پيشنهاد داده اند.

- طرح اول:

3-1- مقدمه

اين طرح در مرجع [4] يعني مقاله “RNS Arithmatic Multiplier for Medium and large Moduli”  بيان شده. در مقدمه آن اشاره شده است كه طرحهاي بر اساس ROM براي پيمانه هاي كوچك مفيد هستند ولي براي پيمانه هاي متوسط و بزرگ بايد از طرحهايي كه هم از ROMهاي كوچك و هم از عناصر رياضي بهره مي برند استفاده كرد كه طرح مورد نظر چنين حالتي دارد.

3-2- بررسي سوابق

براي ضرب پيمانه اي مي توان از ضرب و تبديل هاي متوالي استفاده كرد [21],[20] كه اصلاً روش بهينه اي نيست. بهمين دليل جستجو براي روشهاي بهتر در جريان است. عمده كارهاي انجام شده بر روي پيمانه هاي خاص مثل  يا پيمانه هاي كوچك مي باشد [31]-[22]. طرح [22] پياده سازي ضرب كننده اي است كه پيمانه هاي آن اعداد اول بشكل k

مرجع [25] ضرب كننده با پيمانه هاي بزرگ به شكل () را مطرح كرد. [29] ضرب كننده پيمانه اي را مطرح كرده از Factored decomposition بهره گرفته و در آن پيمانه ها مي توانند اعداد غير اول باشد.

عمده اين روشها بر اساس بكارگيري عناصر رياضي binary-based هستند و هيچ كدام بجز طرح [16] براي استفاده از محاسبات مانده اي
(Residue Arithmatic) طراحي نشده اند.

3-3- الگوريتم

دو باقيمانده Y, X (Residue) را در نظر بگيريد هدف محاسبه |XY|m (حاصلضرب X و Y در پيمانه m) مي باشد. هر دو عدد را مي توان با n بيت نمايش داد:

كه در آن ها n برابر است:

و  و  بيت هاي باينري X و Y مي باشند. حاصلضرب X و Y را مي توان به صورت زير نمايش داد.

با بسط عبارت فوق داريم:

كه مي توان نوشت:

(3-1)

حالا  را به صورت زير تعريف مي كنيم:

vj =                   (3-2)

بنابراين رابطه (3-1) به صورت زير بازنويسي مي شود:

                                                                  (3-3)

و براي محاسبه  معادله بالا به صورت زير در مي آيد:

                                                             (3-4)

3-4- پياده سازي سخت افزاري

شكل بلوكي سخت افزار اين طرح را در شكل (3-1) مشاهده مي كنيد. همانطور كه مشاهده مي شود، طرح پيشنهادي در چهارطبقه پياده شده است.

با دقت در رابطه (3-4) در مي يابيم كه براي پياده سازي اين طرح بايد تمام  را محاسبه كرده و در انتها به صورت پيمانه اي با هم جمع كنيم. بررسي vj در رابطه (3-2) مشخص مي كند كه vj تعداد يك هاي نمايش باينري عبارت  مي باشد.

مراجع

[1] D.E. knuth, the Art of Computer Programming Vol.2/Seminumerical Algorithms, Third Edition, 1998.

[2] P.L. Montgomery, “Modular Multiplication without trival division”, Mathematics of Computation, 44(170); 519-521, April 1985

[3] A.A. Hiasat, “New Efficient Structure for a Modular Multiplier for RNS”, IEEE Transaction on Computers, Vol 49,pp. 170-174 Feb 2000

[4] A.A. Hiasat, “RNS Arithmatic Multiplicr for Medium and Large Moduli”, IEEE  transaction on Circuit and systems-11: Analog and digital Signal processing,” vol. 47, No.q, pp 931-940, sep 2000

[5] D.Pearson, “A parallel implementation of RSA”,  Proceedings in the symposium on Computer, Arithmatic, pp 110, July 1996.

[6] K.C posch, R Posch, “Residue Number system: a key to parallelism in public key cryptography.” IEEE Transaction, Vol.32, no.2, pp:332-335, July 1992.

 [7] G.A. Jullien, “Implementation of Multiplication, Modulo a Prime Number, with Application to Theoritic Transforms,” IEEE Transaction on Computers Vol.29,no.10,pp 899-905, oct 1980.

[8] M.soderstand and Cvernia, “A High speed low-cost modulo P, Multiplier with RNS Arithmatic Application”, Proc. IEEE, Vol 68, pp. 529-532, Apr. 1980

[9] D.Radhakrishan and Y.Yuan, “Novel Approches to the design of VLSI RNS Multipllier”, IEEE Transaction on Circuits and systems-II; Analog and digital signal processing. Vol 39 pp 52-57, Jan 1992.

[10] M Dugdale, “Residue Multipliers Using Factor Decomposition,” IEEE Transaction on Circuits and systems, II: Analog and Digital signal Processing, Vol 41, pp 623-627. Sept 1994.

[11] A.S. Ramnarayan, “Practicul Realization of mod p,p Prime Multipliers,” Electronic Letters. Vol. 16, pp 466-467, June 1980

[12] F.J. Taylor, “A VLSI Residue Arithmatic Multiplier.” IEEE Trans. Computers, Vol 341, no.6, pp.540-546, June 1982.

[13] A.A. Hiasat, “A memory-less mod (2n+1) Residue Multiplier,” Electronic Letters, Vol. 28, pp. 414-415, Jan 1991

[14] C.D, walter, “Systolic Modular Multiplier,” IEEE Trans computers, Vol. 42 no.3. pp. 375-378. Mar 1993

[15] E.Di Claudio, F Piazza and G.Orlandi, “Fast Combinational RNS multiplier for DSP Applications, “IEEE Iran. Computers, Vol.44 no.5, pp. 624-633. May 1985.

[16] 6.Alia, E.Martinelli, “A VLSI Modulo m multiplier,” IEEE Irans on Circuits and system II Analog and Digital Signal Processing, vol 42, pp 725-729, Nov. 1995.

[18] A wrzyszcz, D Milford and E.Duglas, “A new Approach to Fixed-Coeffient inner product over finite Rings,” IEEE Trans computer, Vol 47, no.7, pp 760-776, July 1998.

[19] Si Piestrak “Design of residue generators and Multioperand modular adders using carry-save Adders, “IEEE Trans. Comput. Vol. 43 pp. 6877. Jan 1994.

[20] M. Soderstrand, M. A. W. Jenkins, G. Jullien, and F. Taylor, Eds., Residue Number System Arithmetic: Modern Applications in Digital Signal Processing. Piscataway, NJ: IEEE Press, 1986.

[21] N. Szabo and R. Tanaka, Residue Arithmetic and Its Applications to Computer Technology. New York: McGraw Hill, 1967.

[22] A. S. Ramnarayan, “Practical realization of mod p,p prime multiplier” Electron. Lett., Vol. 16, pp. 466-467, June. 1980.

[23] M. Soderstrand and C. Vernia, “A high-speed low-cost modulo Pi multiplier with RNS arithmetic application,” Proc. IEEE, vol. 68, pp. 529-532, Apr. 1980.

[24] G. A. Jullien, “Implementation of multiplication, modulo a prime number, with applications to theoretic transforms,” IEEE Trans comput., Vol. C-29, pp. 899-905, Oct. 1980.

[25] F. J. Taylor, “ Large moduli multipliers for signal processing,” IEEE Trans. Circuits Syst., Vol. CAS-28, pp. 731-436, July 1981.

[26] F. J. Taylor, “A VLSI residue arithmetic multiplier,” IEEE Trans Comput., Vol. C-31, pp. 540-546, June 1982.

[27] F. J. Taylor and Huandg, “An autoscale residue multiplier,” IEEE Trans. Comput., Vol. C-31, pp. 321-325, Apr. 1982.

[28] A. Hiasat, “A memoryless mod  residue multiplier,” Elecron. Lett., Vol. 28, pp. 414-415, Jan. 1991.

[29] M. Dugdale, “Residue multipliers using factored decomposition,” IEEE Trans. Circuits Syst. II, Vol, 41, pp. 623-627, Sept. 1994.

[30] A. Haisat, “Semi- Custom VLSI design for RNS multipliers using combinational logic approach,” in Proc. 3rd IEEE Int. Conf. Electronics. Circuits and Systems (ICECS’96), Vol. 2, Oct. 1996, pp. 935-938.

[31] D. Radhakrishnan and Y. Yuan, “Novel approaches to the design of VLSI RNS multiplier,” IEEE Trans. Circuits Syst. II, Vol. 39, pp. 52-57, Jan. 1992.

[32] Markus A. Hitz and Erich Kaltofen. Integer division in residue number systems. IEEE Transactions on Computers, 44(8): 983-989, August 1995.

[33]http://www.iis.ee.ethz.ch/zimmi/publication/comp-arith-otes.ps.gz

[34] P. SINHA, “Fast Parallel Algorithms for Binary Multiplication and Their Implementation on Systolic Architectures,” IEEE Transactions on Computers, Vol. 38, No.3, March 1989.

[35] K.C.Posch, R.Posch, “Modulo Reduction In Residue Number Systems,” IEEE Transactions on Parallel and distributed systems, Vol.6, No. 5, May 1995.

[36] R. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Commun. ACM, pp. 120-126, 1978.

[37] K. C. Posch and R. Posch, “Approaching encryption at ISDN speed using partial parallel modulus multiplication,” Microprocessing and Microprogramming. Amsterdam, The Netherlands: North-Holand, 1990, Vol. 29, pp. 177-184.