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

هدف از این پروژه مقایسه چهار طرح ضرب کننده RNS می باشد. بدین منظور با بهره گیری از پیاده سازی این چهار طرح با نرم افزار VHDL به مقایسه آنها می‌پردازیم. RNS یک روش نمایش اعداد است که در آن هر عدد به وسیله باقی مانده‌های تقسیم آن بر مجموعه ای از اعداد دو به دو نسبت به هم اول نمایش داده
می شود. با کمک قضیه باقیمانده چینی، اثبات می شود که در RNS نمایش هر عدد منحصر به فرد می باشد برای ضرب در RNS نیاز به ضرب پیمانه ای خواهد بود. روشهای ضرب پیمانه ای بر حسب اینکه کاهش به پیمانه، در کدام مرحله ضرب انجام گیرد. به دو دسته «کاهش در حین ضرب (RDM)» و «کاهش بعد از ضرب (RAM)» تقسیم می شوند. دو طرح اول این پروژه با تکنیک RAM و دو طرح دوم با تکنیک RDM کار می‌کنند.

مقدمه

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

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

کاربردهای RNS

سیستم عددی باقیمانده در چند دهه اخیر مورد توجه قرار گرفته، زیرا می توان بعضی از اعمال ریاضی را تحت RNS به صورت چند مجموعه زیر عمل ریاضی تقسیم کرد. ولی به دلیل اینکه این اعمال فقط شامل ضرب، جمع و تفریق هستند از RNS در محاسبات “خاص منظوره” استفاده می شود. RNS در پیاده سازی سریع مسائلی که شامل تصحیح و تشخیص خطا در سیستم های Fault-tolerant و سیستم‌های پردازش سیگنال هستند کاربرد دارد. کاربردهایی از قبیل تبدیل فوریه سریع، فیلتر دیجیتال و پردازش تصویر از اعمال ریاضی سریع RNS استفاده می کند. RNS راه خود را در کاربردهایی مثل تبدیلات تئوری اعداد و تبدیل فوریه گسسته پیدا کرده است. همچنین مستقل بودن رقم های باقیمانده باعث می شود که رخ دادن خطا در یک رقم به رقم های بعدی منتقل نشوند که این مساله، باعث ایجاد یک معماری Fault-tolerant خواهد شد.

روشهای ضرب پیمانه ای

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

جمع بندی

با بررسی نتایج پیاده سازی ها در می یابیم که طرحهای یک و دو برای مواردی مناسب هستند که هدف خود ضرب RNS باشد ولی طرحهای سه و چهار وقتی مناسب هستند که از ضرب RNS به عنوان هسته توان رسانی استفاده می شود. دلیل این امر وجود تبدیلات بین سیستم های RNS و نیز خطاهای قابل رفع در روش های RDM است.

مورد دیگر این است که در طرحهای سه وچهار پیمانه ضرب ربطی به سیستمهای عددی RNS ندارد و در واقع از RNS بعنوان کمک عملیات بهره می برد، ولی در طرحهای یک و دو اعداد در خود RNS ضرب می شوند. در اصل طرحهای یک و دو گونه ای از ضرب پیمانه ای هستند.

با توجه به کاربردهای بالا در مواردی که عملیات مورد نظر ما توسط طرح اول و دوم قابل پیاده سازی باشد بهتر است که از این دو طرح استفاده کرد. که از بین این دو طرح اول از لحاظ تاخیر و مساحت ارجحیت دارد؛ ولی در مواردی که کاربرد ما محدود به بکارگیری طرح سوم یا چهارم می شود باید دید که کدام یک از دو پارامتر تاخیر و مساحت برای ما مهم است و پس از آن به ترتیب طرح سوم یا چهارم برگزید.

1- مقدمه 1

• 1-1 سیستم عددی باقیمانده 1
• 1-2 قضیه باقیمانده های چینی 2
• 1-3 کاربردهای RNS 3

2- روشهای ضرب پیمانه ای – 5

• 2-1 روش مونتگمری 5
• 2-2 بررسی اجمالی روشهای موجود پیاده سازی ضرب در RNS 6
• 2-3 نکاتی پیرامون چهار طرح مورد نظر 7

3- طرح اول 8

• 3-1 مقدمه 8
• 3-2 بررسی سوابق 8
• 3-3 الگوریتم 9
• 3-4 پیاده سازی سخت افزاری 10
• 3-5 محاسبه پیچیدگی مساحت و تاخیر طرح اول 13

4- طرح دوم 15

• 4-1 مقدمه 15
• 4-2 بررسی سوابق – 15
• 4-3 الگوریتم 15
• 4-4 پیاده سازی سخت افزاری 18
• 4-5 محاسبه پیچیدگی مساحت و تاخیر طرح دوم 20

5- طرح سوم 21

• 5-1 تبدیل سیستم RNS (Residue Conversion) 28
• 5-2 پیاده سازی سخت افزاری 30
  • 5-2-1 پیاده سازی تبدیل RNS 31
  • 5-2-2 پیاده سازی بخش اصلی الگوریتم (الگوریتم مونتگمری با RNS) 34
• 5-3- محاسبه پیچیدگی مساحت و تاخیر طرح سوم – 36
  • 5-3-1 عناصر وابسته به ROM 36
  • 5-3-2 عناصر ریاضی 36
  • 5-3-3 تاخیر و مساحت تبدیل کننده RNS استاندارد 37
  • 5-3-4 محاسبه مساحت و تاخیر تبدیل کننده RNS سریع 44
  • 5-3-5 مساحت و تاخیر طرح سوم 50
• 5-4 نتایج پیاده سازی در طرح سوم – 56

6- طرح چهارم 58

• 6-1 بیان مقاله در مورد سیستم RNS – 59
• 6-2 بیان مقاله از ضرب پیمانه ای بدون تقسیم (روش مونتگمری) 60
• 6-3 بررسی صحت الگوریتم 62
• 6-4 روش تبدیل RNS 66
• 6-5 پیاده سازی سخت افزاری 67
  • 6-5-1 تبدیل RNS ناقص 68
  • 6-5-2 پیاده سازی بخش اصلی طرح چهارم (الگوریتم مونتگمری) 68
• 6-6 محاسبه پیچیدگی تاخیر و مساحت طرح چهارم 70
  • 6-6-1 محاسبه تاخیر و مساحت تبدیل RNS ناقص 70
  • 6-6-2 محاسبه تاخیر و مساحت در طرح چهارم 72
• 6-7 نتایج شبیه سازی در طرح چهارم 80

7- مقایسه طرح ها وجمع بندی – 81

• 7-1- مقایسه چهار طرح 81
• 7-2- جمع بندی – 98

8- مراجع

9- ضمائم

• الف – کدهای VHDL طرح اول
• ب – کدهای VHDL طرح دوم
• ج – کدهای VHDL طرح سوم
• د – کدهای VHDL طرح چهارم
• هـ – MOMA

منابع

1. D.E. knuth, the Art of Computer Programming Vol.2/Seminumerical Algorithms, Third Edition, 1998.
2. P.L. Montgomery, “Modular Multiplication without trial 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 Arithmetic Multiplier 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, Arithmetic, 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 Theoretic 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 Arithmetic Application”, Proc. IEEE, Vol 68, pp. 529-532, Apr. 1980
9. D.Radhakrishnan and Y.Yuan, “Novel Approaches to the design of VLSI RNS Multiplier”, 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, “Practical Realization of mod p,p Prime Multipliers,” Electronic Letters. Vol. 16, pp 466-467, June 1980
12. F.J. Taylor, “A VLSI Residue Arithmetic 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.
17. A wrzyszcz, D Milford and E.Douglas, “A new Approach to Fixed-Coefficient inner product over finite Rings,” IEEE Trans computer, Vol 47, no.7, pp 760-776, July 1998.
18. Si Piestrak “Design of residue generators and Multi Operand modular adders using carry-save Adders, “IEEE Trans. Comput. Vol. 43 pp. 6877. Jan 1994.
19. 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.
20. N. Szabo and R. Tanaka, Residue Arithmetic and Its Applications to Computer Technology. New York: McGraw Hill, 1967.
21. A. S. Ramnarayan, “Practical realization of mod p,p prime multiplier” Electron. Lett., Vol. 16, pp. 466-467, June. 1980.
22. M. Soderstrand and C. Vernia, “A high-speed low-cost modulo P_i multiplier with RNS arithmetic application,” Proc. IEEE, vol. 68, pp. 529-532, Apr. 1980.
23. 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.
24. F. J. Taylor, “ Large moduli multipliers for signal processing,” IEEE Trans. Circuits Syst., Vol. CAS-28, pp. 731-436, July 1981.
25. F. J. Taylor, “A VLSI residue arithmetic multiplier,” IEEE Trans Comput., Vol. C-31, pp. 540-546, June 1982.
26. F. J. Taylor and Huang, “An autoscale residue multiplier,” IEEE Trans. Comput., Vol. C-31, pp. 321-325, Apr. 1982.
27. A. Hiasat, “A memoryless mod  residue multiplier,” Electron. Lett., Vol. 28, pp. 414-415, Jan. 1991.
28. M. Dugdale, “Residue multipliers using factored decomposition,” IEEE Trans. Circuits Syst. II, Vol, 41, pp. 623-627, Sept. 1994.
29. A. Haisat, “Semi- Custom VLSI design for RNS multipliers using combinational logic approach,” in Proc. 3^rd IEEE Int. Conf. Electronics. Circuits and Systems (ICECS 96), Vol. 2, Oct. 1996, pp. 935-938.
30. 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.
31. Markus A. Hitz and Erich Kaltofen. Integer division in residue number systems. IEEE Transactions on Computers, 44(8): 983-989, August 1995.
32. P. SINHA, “Fast Parallel Algorithms for Binary Multiplication and Their Implementation on Systolic Architectures,” IEEE Transactions on Computers, Vol. 38, No.3, March 1989.
33. K.C.Posch, R.Posch, “Modulo Reduction In Residue Number Systems,” IEEE Transactions on Parallel and distributed systems, Vol.6, No. 5, May 1995.
34. R. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Commun. ACM, pp. 120-126, 1978.
35. K. C. Posch and R. Posch, “Approaching encryption at ISDN speed using partial parallel modulus multiplication,” Microprocessing and Microprogramming. Amsterdam, The Netherlands: North-Holland, 1990, Vol. 29, pp. 177-184.