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

دلیل این امر این است که من اخیراً به آن فکر کردم و هنوز در مورد آن به کسی نگفته ام. با این حال ، عملکرد کد ، مانند عملکرد پردازنده ، دارای ویژگی های عینی است که قابل اندازه گیری است. این مقاله به طور خاص در مورد عملکرد کدی است که توسط هسته پردازنده اجرا شده است.

عملکرد کد چگونه اندازه گیری می شود؟ از آنجا که من اولین کسی هستم که در این مورد صحبت کردم ، پس به حق کاشف آن را در RTT-shkakh اندازه خواهم گرفت ؛).

حالا جدی در پردازنده های مدرن ، تحولات اصلی اعمال روی اعداد 32 بیتی است ، همه چیزهای دیگر به طور کلی عجیب و غریب هستند. بنابراین ، ما چیز اصلی را مورد توجه قرار خواهیم داد - عملیات با شماره های 32 بیتی. به نظر شما چند پردازنده 32 بیتی می تواند همزمان انجام دهد؟

دانش آموز جواب می دهد - یکی ، معلم او فکر می کند و می گوید چهار نفر وجود دارد ، یک حرفه ای - که فقط دوازده عمل وجود دارد.

بنابراین ، کد برنامه ای که تمام دستگاه های اجرایی پردازنده را به طور همزمان در کل مدت زمان اجرای کد بارگیری می کند ، دارای عملکردی برابر با 12 RTT-shekel است. بیشترین! صادقانه بگویم ، من قبلا چنین کدی را ننوشته ام ، اما در این مقاله سعی خواهم کرد که خودم را تلاشی کنم.

من ثابت خواهم کرد که کد با اجرای همزمان دوازده عمل 32 بیتی امکان پذیر است

کد برنامه ای که از یک واحد اجرایی در هسته پردازنده استفاده می کند به طور طبیعی عملکردی برابر با 1 RTT خواهد داشت. برنامه های تولید شده توسط کامپایلرهای زبان سطح بالا و مترجمان ماشین مجازی می توانند از چنین عملکرد کدی برخوردار باشند. تصور نکنید که معیار استفاده از پردازنده که در OS Task Manager مشاهده می کنید می تواند به عنوان یک معیار هدف برای اثربخشی کد شما عمل کند. بار هسته پردازنده می تواند 100٪ باشد ، اما کد برنامه از یک دستگاه اجرایی در آن استفاده می کند (عملکرد 1 RTT). در این حالت ، با 100٪ بار ، هسته پردازنده با 1/12 حداکثر عملکرد خود کار می کند. به عبارت دیگر ، هنگامی که حداکثر استفاده از CPU در Windows Task Manager نشان داده شود ، عملکرد واقعی آن می تواند از 1 تا 12 RTT متغیر باشد. با مشاهده بار 100٪ روی هر هسته پردازنده ، تصور اینکه همه دستگاه های اجرایی در این هسته کار می کنند ، به هیچ وجه اشتباه است!

تنها معیار ارزیابی غیرمستقیم کار هسته پردازنده با حداکثر کارایی ، مصرف برق و در نتیجه سر و صدای کولر است. اکنون ، اگر کولر پر سر و صدا باشد ، بله - بار به حداکثر رسیده است. با این حال ، وقت آن است که با مفاهیم کلی به پایان برسیم و به تمرینات سخت بپردازیم.

اجرای سنتی GOST 28147-89

من یک متخصص امنیت اطلاعات نیستم ، اما هنوز با مبحث رمزگذاری آشنا هستم. از من الهام گرفته شد که روی رمزگذاری جریان متقارن تمرکز کنم ، به طور خاص با یک رمزنگار حرفه ای که به شدت برای او احترام قائلم. و با پرداختن به این مبحث ، سعی کردم دقیقاً به خوبی انجام دهم ، و نه فقط به خوبی ، بلکه به سرعت ، حداکثر تعداد عملیات را در واحد زمان انجام دهم. به عبارت دیگر ، من با کار نوشتن کد برنامه با حداکثر مقدار RTT روبرو بودم.

تحول رمزنگاری مطابق با GOST 28147-89 برای رمزگذاری جریان اطلاعات در کانال های ارتباطی و درایوهای دیسک استفاده می شود.

در حال حاضر ، از اجرای نرم افزار این GOST در RON پردازنده مرکزی به طور گسترده استفاده می شود. در روش های شناخته شده اجرای GOST ، تمام اطلاعات محرمانه (کلیدهای رمزگذاری ، بلوک های جایگزین) در RAM قرار دارند. این قابلیت اطمینان رمزگذاری را کاهش می دهد ، زیرا با داشتن یک حافظه اصلی ، می توان تمام عناصر مخفی تحول رمزنگاری را به طور کامل آشکار کرد. بعلاوه ، این روش به دلیل قرارگیری اجسام اصلی رمزنگاری در OP و بارگذاری ناقص محرک های ALU ، محدودیت عملکردی دارد. پردازنده های مدرن ، با اجرای روشی رمزنگاری شده طبق روشی شناخته شده ، می توانند سرعت رمزگذاری 40-60 مگابایت در ثانیه را فراهم کنند. و اگر واقعاً تا آخر می فهمید ، دلیل پایین بودن سرعت و امنیت ضعیف تحول رمزنگاری ، اجرای نرم افزار بلوک جایگزینی است. برای توضیحات آن در GOST ، شکل را ببینید. یکی

طبق بند 1.2 GOST ، این بلوک جایگزینی های tetrad (چهار بیتی) را با یک کلمه 32 بیتی پیاده سازی می کند ، اما معماری پردازنده x86 / 64 و سیستم دستورالعمل آن قادر به دستکاری م theثر tetrad ها نیستند.

برای اجرای نرم افزاری بلوک جایگزینی ، جداول خاصی در RAM استفاده می شود که در مرحله راه اندازی اولیه عملکرد رمزنگاری آماده شده است. این جداول گره های جایگزین تترادهای مجاور را به جداول بایت 8x8 بیتی ترکیب می کنند ، بنابراین ، چهار جدول 256 بایتی در RAM قرار دارد.

در پیاده سازی های پیشرفته تر ، این جداول اندازه 1024 بایت دارند (256 کلمه از چهار بایت). این کار به منظور پیاده سازی یک تغییر چرخشی 11 موقعیتی اضافی از کلمه 32 بیتی حاصل از جایگزینی (عملیات بعدی الگوریتم تبدیل طبق GOST) در جداول انجام می شود. نمونه ای از اجرای GOST با توجه به این روش در ضمیمه 1 (بر روی دیسک) نشان داده شده است.

اطلاعات بلوک جایگزین جزء مخفی عملکرد رمزنگاری است (همانطور که در GOST فرموله شده است ، شکل 2 را ببینید).

قرار دادن این جداول با کلیدهای بلوک جایگزینی در OP با الزامات GOST (بند 1.7) مغایرت دارد ، زیرا اطلاعات محرمانه در دسترس برنامه های شخص ثالثی است که در رایانه نصب می شوند. FSB ، که همچنین پیاده سازی نرم افزاری رمزگذاری را مطابق با GOST تأیید می کند ، به لطف آن ، به بیان ملایم ، تسلیم کننده این نقض را بررسی می کند. اگر FSB همچنان به وجود "برگ انجیر" نیاز دارد - برای قرار دادن کلیدها در OP کلیدها را با عمل XOR مخفی می کند ، پس برای بلوک های جایگزین OP چیزی لازم نیست ، آنها در متن واضح ذخیره می شوند.

به طور خلاصه ، FSB از چنین پیاده سازی نرم افزاری روش رمزنگاری صرف نظر می کند ، با وجود کاهش آشکار قدرت چنین راه حل و نقض مستقیم نیازهای خود مطابق با GOST (بند 1.7). و این به رغم روشهای شناخته شده شکستن رمزها با خواندن یک حافظه تخلیه است ...

ما کمی بعد به موضوع ذخیره کلیدها و بلوک های جایگزین در رجیسترهای داخلی پردازنده باز می گردیم (یک راه حل زیبا و سریع وجود دارد) ، اما در حال حاضر ما فقط کلیدهای رمزگذاری را در ثبت های MMX ذخیره می کنیم ، این قابل اطمینان تر است .

اما متن کافی ، در چارچوب موضوع مورد بررسی مهم است که این کد برنامه عملکردی برابر با 1 RTT-shku داشته باشد. حال بیایید کدی با عملکرد 2 RTT بنویسیم.

اجرای چند رشته ای GOST 28147-89

تنها راه برای سرعت بخشیدن به روشهای رمزنگاری در الگوریتم شناخته شده ، معرفی چند رشته است. معنای چنین تغییری در اجرای الگوریتم محاسبه همزمان چندین بلوک داده به طور موازی است.

منظور بیشتر برنامه نویسان از پردازش موازی منحصراً کار چندین هسته پردازنده است که از طریق وقفه ها و سمافورهای حافظه همزمان می شوند.

با این وجود ، نوع دیگری از پردازش داده های موازی در یک هسته پردازنده وجود دارد. بگذارید این ایده غیرقابل انکار را توضیح دهم.

پردازنده های مدرن حداقل شامل دو یا حتی سه تا شش دستگاه منطقی حسابی هستند. این ALU ها (FPU ها ، واحدهای حساب آدرس و غیره) می توانند مستقل از یکدیگر کار کنند ، تنها شرط عملکرد موازی آنها اشیا software نرم افزاری غیر همپوشانی که با آنها کار می کنند نیست. به عبارت دیگر ، در دستورالعمل هایی که همزمان ALU ها را اجرا می کنند ، آدرس حافظه و شماره ثبت باید متفاوت باشد. یا نباید هیچگونه فعالیت نوشتاری در رجیسترهای عمومی و آدرسهای حافظه وجود داشته باشد که توسط واحدهای مختلف پردازنده قابل دسترسی هستند.

بارگذاری کار همه ALU ها توسط یک واحد سخت افزاری خاص درون هسته پردازنده کنترل می شود - یک برنامه ریز که کد اجرایی را به جلو ، تا عمق 32-64 بایت اسکن می کند. اگر زمانبند دستوراتی را که می توانند بدون درگیری روی ALU اجرا شوند تشخیص دهد ، آنها را به طور همزمان در دستگاه های اجرایی مختلف اجرا می کند. در این مورد ، شمارنده دستورات اجرا شده فرمان اجرایی را نشان می دهد (چندین مورد از آنها در چنین طرحی وجود دارد) ، پس از آن همه دستورات قبلاً اجرا شده اند.

بیشتر توالی های برنامه که به طور خودکار تولید می شوند (توسط کامپایلرها) نمی توانند تمام ALU ها و FPU های مستقر در هسته پردازنده را بارگیری کنند. در این حالت ، سخت افزار پردازنده بیکار است که عملکرد قابل توجه آن را به میزان قابل توجهی کاهش می دهد. توسعه دهندگان پردازنده این موضوع را درک می کنند و در صورت عدم استفاده کامل از سخت افزار ، حالت های افزایش فرکانس اصلی را معرفی می کنند. سیستم های Hypertrading نیز برای این منظور در نظر گرفته شده اند و من از این سیستم برای "فشرده سازی" کد در حداکثر در آینده استفاده خواهم کرد.

کامپایلرها ، حتی بهینه ترین ها و حتی بیشتر از آن - موتورهای ماشین مجازی ، از نظر عملکرد نمی توانند کدهای بهینه شده تولید کنند. فقط یک برنامه نویس با دانش مهندسی می تواند چنین کد بهینه شده ای را بنویسد و ابزار نوشتن آن منحصراً یک اسمبلر است.

یک نمونه معمولی از امکان اجرای چندین رشته برنامه مستقل بر روی یک هسته پردازنده ، اجرای GOST است که در دو رشته در یک هسته پردازنده اجرا می شود. ایده پشت کد ساده است: دو بلوک داده برای رمزگذاری / رمزگشایی وجود دارد ، اما یک هسته پردازنده وجود دارد که تبدیل را انجام می دهد. تبدیل این دو بلوک داده به صورت متوالی امکان پذیر است و این کار تاکنون انجام شده است. در این حالت ، زمان لازم برای انجام تحولات دو برابر می شود.

اما می توانید متفاوت عمل کنید: دستورات جایگزین مربوط به پردازش بلوک های مختلف داده. این گزینه ها به صورت گرافیکی در شکل نشان داده شده است. 3

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

در زیر مثالی از دستورات interleaving از موضوعات مختلف پردازشی وجود دارد. در این مورد ، دستورات مربوط به بلوک های داده مختلف در هم آمیخته می شوند. برنامه ریز فرامین مستقل از یکدیگر را انتخاب می کند و آنها را برای اجرا به ALU1 و ALU2 می فرستد. گروه بندی دستورات جریان اول و دوم روی این ALU ها به طور خودکار انجام می شود ، زیرا گروه بندی دستورات با درگیر شدن با داده های مشترک روی همان دستگاه اجرایی در الگوریتم زمانبند گنجانده شده است.

برای اینکه چنین کد برنامه ای بدون خرابی ALU کار کند ، لازم است که هر رشته برنامه با مجموعه رجیسترهای خاص خود کار کند. حافظه پنهان در این طرح به یک گلوگاه تبدیل می شود (فقط دو پورت برای خروجی داده دارد) ، بنابراین ما کلیدها را در رجیسترهای MMX ذخیره می کنیم. از آنجا که در این حالت گره های جایگزین (و shift) حافظه فقط خوانده می شوند ، می توانند برای هر دو موضوع برنامه مشترک باشند.

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

روش رمزگذاری موازی فقط برای حالت 64 بیتی عملکرد پردازنده به طور مثر اجرا می شود ، زیرا در این حالت تعداد کافی RON وجود دارد (به اندازه 16!). نمونه ای از اجرای GOST با توجه به این روش در ضمیمه 2 (بر روی دیسک) نشان داده شده است.

واضح است که این اجرای GOST دارای عملکرد 2 کد RTT است. حالا بیایید ببینیم این چگونه بر زمان اجرا تأثیر می گذارد.

چرخه رمزگذاری برای یک جریان (ضمیمه 1) 352 چرخه است و در این مدت 8 بایت داده محاسبه می شود ؛ برای اجرای دو رشته ای GOST (ضمیمه 2) ، 416 چرخه پردازنده مورد نیاز است ، اما 16 بایت محاسبه می شود. بنابراین ، سرعت تبدیل حاصل از 80 به 144 مگابایت برای پردازنده 3.6 گیگاهرتز افزایش می یابد.

یک تصویر جالب به دست می آید: کد دقیقاً دو برابر دستورات دارد و فقط 15 درصد زمان بیشتری طول می کشد تا اجرا شود ، اما من فکر می کنم خوانندگان قبلاً دلیل این پدیده را درک کرده اند ...

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

اگر کسی حرف من را قبول نکند ، برای چنین کافران ، برنامه های آزمایشی با شمارنده های ساعت بر روی دیسک متصل می شوند. این برنامه ها در کدهای منبع ، به طور طبیعی در مونتاژ وجود دارد ، بنابراین فرصتی برای بررسی سخنان من وجود دارد و در عین حال برخی از ترفندهای رمزگذاری حرفه ای را جاسوسی می کنم.

استفاده از SSE-ثبت و دستورالعمل های AVX پردازنده های مدرن برای اجرای GOST 28147-89

پردازنده های مدرن معماری x86 / 64 شامل مجموعه ای از ثبات های 16 بایت SSE و FPU های تخصصی (حداقل دو) برای انجام عملیات مختلف بر روی این ثبات ها هستند. امکان پیاده سازی GOST بر روی این تجهیزات وجود دارد و در این مورد ، گره های جایگزین را می توان نه در قالب جداول در RAM ، بلکه مستقیماً در ثبت های اختصاصی SSE قرار داد.

یک ثبت SSE می تواند همزمان دو جدول با 16 ردیف را در خود جای دهد. بنابراین ، چهار رجیستر SSE به شما امکان می دهد تمام جداول جایگزین را به طور کامل در خود جای دهید. تنها شرط برای چنین قرارگیری نیاز به interleaving است ، که طبق آن تترادهای یک بایت باید در رجیسترهای مختلف SSE قرار گیرند. علاوه بر این ، توصیه می شود که میزان شیب پایین و بالاتر بایت ورودی ، به ترتیب در شیب پایین و بالاتر ثبت های SSE قرار گیرد.

این الزامات با بهینه سازی مجموعه موجود دستورات AVX دیکته می شود. بنابراین ، هر بایت رجیستر SSE شامل دو تتراد مربوط به بایت های مختلف رجیستر ورودی بلوک جایگزینی خواهد بود ، در حالی که موقعیت بایت در ثبات SSE منحصراً با شاخص موجود در جدول جایگزینی بلوک جایگزینی مطابقت دارد.

نمودار یکی از مکانهای احتمالی گرههای جایگزین در ثباتهای SSE در شکل نشان داده شده است. 4

قرار دادن اطلاعات محرمانه گره های جایگزینی در ثبات های SSE ، امنیت روش رمزنگاری را افزایش می دهد ، اما در صورت تحقق شرایط زیر ، جداسازی کامل این اطلاعات محرمانه امکان پذیر است:

• هسته پردازنده در حالت میزبان hypervisor قرار گرفته است و بلوک وقفه (APIC) به زور در آن غیرفعال می شود. در این حالت ، هسته پردازنده کاملاً از سیستم عامل و برنامه هایی که بر روی امکانات رایانه در حال اجرا هستند جدا شده است.
• بارگذاری رجیسترهای SSE و جداسازی هسته محاسباتی قبل از شروع سیستم عامل انجام می شود ؛ انجام این مراحل از ماژول راه اندازی قابل اعتماد (TLS) بهینه است.
• برنامه های روش های رمزنگاری مطابق با GOST در یک منطقه حافظه غیر قابل تغییر در یک دستگاه محاسباتی (BIOS یا در حافظه فلش MDZ) قرار دارند.

تحقق این الزامات تضمین انزوای کامل و تغییرناپذیری کد برنامه رویه های رمزنگاری و اطلاعات محرمانه مورد استفاده در آنها را امکان پذیر می سازد.

برای واکشی کارآمد از ثبات های SSE تترادها ، از سوئیچ های چند ورودی بایت موجود در FPU استفاده می شود. این سوئیچ ها با توجه به شاخص های واقع در یک رجیستر خاص SSE امکان انتقال از هر بایت منبع به هر بایت مقصد را دارند. علاوه بر این ، به طور موازی ، انتقال برای هر 16 بایت گیرنده-ثبات SSE انجام می شود.

با داشتن گره هایی برای ذخیره جایگزینی ها در ثبات های SSE و یک سوئیچ چند ورودی در FPU ها ، می توانیم تحول زیر را در یک واحد جایگزینی سازمان دهیم (شکل 5).

در این طرح ، ثبت ورودی در هر tetrad آدرس سوئیچ مربوطه را تنظیم می کند ، که اطلاعات را از درایوهای گره های جایگزین از طریق گذرگاه داده به ورودی خروجی منتقل می کند. این طرح را می توان به سه طریق سازماندهی کرد:

• برای ایجاد یک طرح تراشه مناسب ، اما این برای ما فوق العاده است.
• برنامه ریزی مجدد میکرو کد و ایجاد دستورالعمل پردازنده برای پیاده سازی این عملکرد در پردازنده های موجود دیگر خیالی نیست ، اما متأسفانه در شرایط فعلی غیر واقعی است.
• بر روی دستورات رسمی AVX برنامه بنویسید. این گزینه ، البته بسیار کارآمد نیست ، اما ما آن را "اینجا و اکنون" پیاده خواهیم کرد. بنابراین این همان کاری است که در ادامه انجام خواهیم داد.

کار کلیدها توسط یک دستور ویژه سه نشانی AVX VPSHUFB کنترل می شود. عملوند اول آن دریافت کننده اطلاعات از سوئیچ ها است ، دوم منبع منبعی است که ورودی سوئیچ ها به آن متصل می شوند. سومین عملوند یک رجیستر کنترل برای سوئیچ ها است که هر بایت آن با یک سوئیچ مربوطه مرتبط است. مقدار موجود در آن شماره جهت را مشخص می کند که سوئیچ اطلاعات را از آن می خواند. برای توضیح این دستور از مستندات رسمی اینتل ، شکل را ببینید. 5. در شکل 6 نمودار عملکرد این دستور را نشان می دهد - فقط نیمی از ثبات های SSE نشان داده شده است ، برای نیمه دوم همه چیز یکسان است.

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

برنامه ای با انتخاب نوت بوک ها از طریق سوئیچ های FPU نوشته شده بود ، اما من حتی شروع به اجرای آن در برنامه نکردم - بسیار رقت انگیز بود. داشتن رجیستری با اندازه 128 بیت و استفاده از تنها 32 بیت در آن غیر حرفه ای است.

به قول معروف ، "پایان ما افق است" ، بنابراین اینگونه فشار دهید ... ما فشار خواهیم داد و در کیسه ها خواهیم گذاشت!

این یک بازی با کلمات نیست ، بلکه یک واقعیت FPU خشن است - ثبات های SSE را می توان به قسمت های مساوی تقسیم کرد و می توان با یک فرمان همان تغییرات را در این قسمت ها انجام داد. برای اینکه پردازنده بتواند این را درک کند ، یک حرف جادویی "P" وجود دارد - یک بسته که در جلوی دستور mnemonic قرار داده شده است ، و حروف جادویی "Q" ، "D" ، "W" ، "B" وجود ندارد. ، که در انتها قرار می گیرند و اعلام می کنند که در این دستور ثبت کننده های SSE در کدام قسمت ها تقسیم می شوند.

ما به حالت دسته ای تقسیم شده ایم که رجیستر SSE به چهار بلوک 32 بیتی تقسیم شده است. بر این اساس ، تمام دستورات با "P" پیشوند قرار می گیرند ، و در پایان - شخصیت "D". این امکان را می دهد که با یک دستور پردازنده همزمان چهار بلوک 32 بیتی را همزمان پردازش کنید ، یعنی چهار بلوک داده را به طور موازی محاسبه کنید.

برنامه ای که این روش را اجرا می کند ، در پیوست 3 ، در همان مکان - همه توضیحات - موجود است.

با این حال ، فشار دهید تا فشار دهید! پردازنده های مدرن حداقل دارای دو FPU هستند و برای بارگیری کامل آنها می توان از دو جریان دستورالعمل مستقل استفاده کرد. اگر به درستی دستورات را از جریان های مستقل جایگزین کنید ، می توانید هر دو FPU را با کار بارگیری کنید و همزمان هشت جریان داده موازی دریافت کنید. چنین برنامه ای نوشته شده است ، و شما می توانید آن را در ضمیمه 4 ببینید ، اما باید با دقت نگاه کنید - می توانید دیوانه شوید. این ، همانطور که می گویند ، "کد برای همه نیست ...".

قیمت صدور

استفاده از ثبات های SSE برای ذخیره گره های جایگزین قابل درک است - این تضمین خاصی را برای جدا کردن اطلاعات محرمانه فراهم می کند ، اما معنی محاسبه عملکرد رمزنگاری در FPU مشخص نیست. بنابراین ، ما زمان اجرای مراحل استاندارد را با استفاده از روش جایگزینی مستقیم مطابق با GOST برای چهار و هشت جریان اندازه گیری کردیم.

سرعت اجرای 472 چرخه پردازنده برای چهار نخ به دست آمد. بنابراین ، برای پردازنده ای با فرکانس 3.6 گیگاهرتز ، یک رشته با سرعت 59 مگابایت در ثانیه و چهار رشته به ترتیب با سرعت 236 مگابایت در ثانیه محاسبه می شود.

سرعت اجرای 580 چرخه پردازنده برای هشت رشته به دست آمد. بنابراین ، برای یک پردازنده 3.6 گیگاهرتزی ، یک موضوع 49 مگابایت در ثانیه و هشت رشته با 392 مگابایت در ثانیه شمارش می شود.

همانطور که خواننده می بیند ، کد موجود در مثال شماره 3 دارای 4 RTT و کد در مثال شماره 4 دارای 8 RTT است. در این مثالها در ثبتهای SSE ، الگوها همانند استفاده از RON است ، فقط زمانبند کارایی آن را کاهش داده است. اکنون 20٪ افزایش مدت زمان با 2 برابر افزایش طول کد فراهم می کند.

علاوه بر این ، این نتایج با استفاده از دستورات AVX جهانی موجود در هر دو پردازنده Intel و AMD به دست آمد. اگر برای پردازنده AMD بهینه سازی کنید ، نتیجه بسیار بهتر خواهد بود. برخلاف روند به نظر می رسد ، اما درست است و به همین دلیل است که: پردازنده های AMD یک مجموعه دستورالعمل اضافی دارند که اصطلاحاً پسوند XOP نامیده می شود و این مجموعه دستورالعمل های اضافی حاوی مواردی هستند که اجرای الگوریتم GOST را بسیار ساده می کنند.

این به دستورالعمل های منطقی burst byte و burst cyclic shift دو دستورالعمل اشاره می کند. مثالهای ارائه شده در پیوستهای 3 و 4 از توالی دستورات جهانی استفاده می کنند که تحول مورد نیاز را اجرا می کنند: در حالت اول ، یک دستور "اضافی" و در حالت دیگر ، چهار دستور اضافی همزمان. بنابراین منابع برای بهینه سازی وجود دارد ، و قابل توجه است.

اگر ما در مورد بهینه سازی بیشتر صحبت می کنیم ، لازم به یادآوری وجود ثبت کننده های 256 بیتی (ثبت کننده های YMM) است که با استفاده از آنها می توانید سرعت محاسبات را دو برابر کنید. اما در حالی که این تنها یک چشم انداز است ، در حال حاضر پردازنده ها هنگام اجرای دستورالعمل های 256 بیتی سرعت خود را بسیار کاهش می دهند (عرض مسیر FPU ها 128 بیت است). آزمایشات نشان داده است که در پردازنده های مدرن ، شمارش 16 نخ در رجیسترهای YMM برنده نیست. اما این فقط در حال حاضر است ، در مدلهای پردازنده جدید ، بدون شک سرعت دستورالعملهای 256 بیتی افزایش می یابد ، و سپس استفاده از 16 رشته موازی به مصلحت تبدیل می شود و منجر به افزایش حتی بیشتر سرعت روش رمزنگاری می شود .

از نظر تئوری ، در صورت وجود دو FPU در پردازنده با عرض مسیر کار هر کدام 256 بیت ، می توانید روی سرعت 600-700 مگابایت بر ثانیه حساب کنید. در این حالت می توانیم در مورد نوشتن کد با بازده 16 RTT صحبت کنیم و این داستان داستانی نیست بلکه آینده ای نزدیک است.

حالت مخلوط

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

در اینجا لازم نیست که روی 50٪ افزایش حساب کنید ، حافظه نهان ، جایی که ماسک های فن آوری در آن ذخیره می شود ، به یک گلوگاه تبدیل می شود ، اما با این وجود می توان 100 مگابایت اضافی را نیز افزایش داد. این گزینه در ضمائم نشان داده نشده است (ماکروها مشابه آنچه در کد 8 RTT استفاده شده است) ، اما در پرونده های برنامه موجود است. بنابراین اگر کسی به امکان رمزگذاری با سرعت 500 مگابایت بر ثانیه بر روی یک هسته پردازنده اعتقادی ندارد ، بگذارید پرونده های آزمایشی را اجرا کند. متنهایی نیز با نظرات وجود دارد تا هیچ کس فکر نکند که من در حال انتشار هستم.

این تمرکز فقط بر روی پردازنده های اینتل امکان پذیر است ، AMD فقط دو FPU برای دو ماژول پردازنده دارد (مشابه حالت هایپرتریدینگ). اما چهار ALU وجود دارد که استفاده از آنها گناه است.

شما می توانید ماژول های پردازنده Bulldozer را به یک حالت شبیه حالت Hypertrading هدایت کنید ، اما تبدیل را بر روی RON در ماژول های مختلف در یک موضوع و در ثبات های SSE در یک موضوع دیگر اجرا کنید و همان 12 RTT را بدست آورید. من این گزینه را آزمایش نکرده ام ، اما فکر می کنم کد 12 RTT به طور م onثرتری روی AMD کار خواهد کرد. علاقه مندان می توانند امتحان کنند ، برنامه های آزمایشی را می توان به راحتی روی "بولدوزرها" کار کرد.

چه کسی به آن نیاز دارد؟

یک سوال جدی ، اما با یک پاسخ ساده - همه به آن نیاز دارند. به زودی همه ما روی ابرها می نشینیم ، هم داده ها و هم برنامه ها را در آنجا ذخیره می کنیم ، و در اینجا ، آه ، چگونه می خواهید گوشه خصوصی و شخصی خود را تجهیز کنید. برای انجام این کار ، باید ترافیک را رمزگذاری کنید و سرعت تبدیل رمزنگاری عامل اصلی تعیین کننده برای یک کار راحت در ابر خواهد بود. انتخاب ما از الگوریتم رمزگذاری کوچک است - یا GOST یا AES.

و ، به طرز عجیبی ، رمزگذاری AES تعبیه شده در پردازنده ها بسیار کندتر به نظر می رسد ، آزمایشات سرعت را در سطح 100-150 مگابایت بر ثانیه نشان می دهد ، و این با اجرای سخت افزاری الگوریتم است! مشکل در شمارش تک رشته ای و بلوک جایگزینی ها است که با بایت کار می کند (جدول 256 ردیف). بنابراین GOST در اجرای معماری x86 / 64 کارآمدتر است ، چه کسی فکر می کرد ...

این زمانی است که ما در مورد سطح دستیابی به سرعت رمزگذاری صحبت می کنیم. و اگر پیچیدگی نظری را در زمینه بهبود کارایی کد در خاطر داشته باشیم ، به احتمال زیاد هیچ کس به آن نیازی ندارد. در سطح 3 تا 6 RTT عملاً هیچ متخصصی وجود ندارد ، کامپایلرها به طور کلی در سطح 1 تا 2.5 RTT کد تولید می کنند و اکثر برنامه نویسان اسمبلر را نمی شناسند و حتی اگر از املای آن مطلع باشند ، دستگاه مدرن را درک نمی کنند. پردازنده و بدون این دانش مونتاژ کننده ، نوعی SI-تیز - تفاوتی ندارد.

اما همه چیز چندان غم انگیز نیست: در "نتیجه نهایی" پس از یک هفته بی خوابی یک الگوریتم جدید برای اجرای GOST وجود دارد ، که عدم ثبت اختراع گناه است. و درخواست های ثبت اختراع (به اندازه سه مورد) قبلاً ثبت و ثبت شده است ، بنابراین ، آقایان ، تجار ، صف آرایی کنید - زنان و کودکان تخفیف می گیرند.

الگوریتم GOST 28147-89 و رمز "ماگما" (GOST R 34.12-2015)

طرح کلی الگوریتم. الگوریتمی که توسط GOST 28147-89 توصیف شده است «سیستم های پردازش اطلاعات. محافظت از رمزنگاری الگوریتم تبدیل رمزنگاری "یک استاندارد داخلی برای رمزنگاری متقارن (قبل از 1 ژانویه 2016) است و برای پیاده سازی در ابزارهای حفاظت از اطلاعات رمزنگاری معتبر که در سیستم های اطلاعات دولتی و در برخی موارد در سیستم های تجاری استفاده می شود ، اجباری است. برای محافظت از اطلاعاتی که یک راز دولتی فدراسیون روسیه است و اطلاعاتی که محرمانه بودن آنها باید مطابق با قوانین فعلی تضمین شود ، مجوز استفاده از اطلاعات رمزنگاری اطلاعات لازم است. همچنین در فدراسیون روسیه ، استفاده از الگوریتم GOST 28147-89 برای حفاظت از سیستم های اطلاعات بانکی توصیه می شود.

الگوریتم GOST 28147-89 (شکل 2.21) بر اساس طرح Feistel است و اطلاعات را در بلوک های 64 بیتی رمزگذاری می کند ، که به دو زیر بلوک 32 بیتی تقسیم می شوند (I ، و R)ساب بلاک کردن R ،توسط تابع تحول گرد پردازش می شود ، پس از آن مقدار آن به مقدار ساب بلاک Lj افزوده می شود ، سپس زیرمجموعه ها عوض می شوند. این الگوریتم بسته به حالت رمزگذاری 16 یا 32 دور دارد ، (محاسبه درج تقلید یا سایر حالت های رمزگذاری).

برنج. 2.21

در هر دور الگوریتم ، تغییرات زیر انجام می شود.

1. همپوشانی کلیدمحتوای زیر بلاک R i modulo 2 32 با کلید گرد اضافه شده است K. Kjقسمت 32 بیتی کلید اصلی است که به عنوان کلید گرد استفاده می شود. الگوریتم GOST 28147-89 ns از یک روش گسترش کلید استفاده می کند ، کلید رمزگذاری اصلی 256 بیتی به عنوان اتصال (اتصال) هشت زیر کلید 32 بیتی (شکل 2.22) نشان داده شده است: K 0 ، K (، K t K ، K A ، K 5 ، K 6 ، K 7.

فرآیند رمزگذاری از یکی از این کلیدهای فرعی استفاده می کند. به

از مرحله 1 تا 24 - به ترتیب مستقیم:

از دور 25 تا 32 - به ترتیب معکوس:

برنج. 22/2 ساختار کلید رمزگذاری الگوریتم GOST 28147-89

2. جایگزینی جداولپس از استفاده از کلید ، ساب بلاک کنید R iبه هشت قسمت اما 4 بیت تقسیم شده است که مقدار هر یک به تنهایی مطابق با جدول جایگزین آن (جعبه S) جایگزین می شود. در مجموع هشت جعبه S - S 0 ، S ، S 2 ، S 3 ، S 4 ، S 5 ، S 6 ، S 7 استفاده می شود. هر جعبه S الگوریتم GOST 28147-89 یک بردار (آرایه تک بعدی) با ^ عناصر از 0 تا 15 است. مقادیر S-box اعداد 4 بیتی است. اعداد صحیح از 0 تا 15

یک عنصر از جدول S-box گرفته شده است ، که شماره ترتیبی آن با مقداری که به ورودی جایگزینی وارد شده مطابقت دارد.

مثال 2.6.

اجازه دهید یک بلوک S به شکل زیر وجود داشته باشد:

بگذارید مقدار 0100 2 = 4 به ورودی این جعبه S داده شود. خروجی جعبه S عنصر چهارم جدول جایگزینی خواهد بود ، یعنی. 15 = 1111 2 (شماره گذاری عناصر از صفر شروع می شود).

افراد جایگزینی طبق استاندارد تعریف نشده اند ، همانطور که برای مثال در رمزگذاری DES انجام می شود. مقادیر قابل تعویض جداول جایگزینی ، تجزیه و تحلیل رمزنگاری الگوریتم را بسیار دشوارتر می کند. در عین حال ، مقاومت الگوریتم اساساً به انتخاب صحیح آنها بستگی دارد.

متأسفانه ، الگوریتم GOST 28147-89 دارای جداول جایگزینی "ضعیف" است ، که با استفاده از آنها الگوریتم می تواند به راحتی با روش های رمزنگاری آشکار شود. در میان "ضعیف" ، برای مثال ، یک جدول بی اهمیت از جایگزینی ها ، که در آن ورودی برابر خروجی است (جدول 2.16).

جدول 2.16

نمونه ای از جعبه S ضعیف

اعتقاد بر این است که مقادیر خاص جداول جایگزین باید مخفی نگه داشته شود و یک عنصر کلیدی طولانی مدت باشد ، به عنوان مثال برای یک دوره بسیار طولانی تر از کلیدهای شخصی معتبر هستند. با این حال ، مقادیر مخفی جداول جایگزین بخشی از کلید نیستند و نمی توانند طول موثر آن را افزایش دهند.

در واقع ، جداول جایگزینی مخفی را می توان با استفاده از حمله زیر محاسبه کرد ، که می تواند در عمل اعمال شود:

• یک کلید صفر تنظیم شده و جستجوی "بردار صفر" انجام می شود ، به عنوان مثال. معنی z = F ( 0) ، کجا F -عملکرد تحول گرد الگوریتم. این مورد نیاز به حدود 32 عملیات رمزگذاری آزمایشی دارد.
• با استفاده از بردار صفر ، مقادیر جداول جایگزینی محاسبه می شود که بیش از 2 11 عملیات طول نمی کشد.

با این حال ، حتی اگر محرمانه بودن جداول جایگزینی نقض شود ، قدرت رمز بسیار بالا می ماند و از حد مجاز پایین نمی آید.

همچنین فرض بر این است که جداول جایگزینی برای همه گره های رمزگذاری در یک سیستم حفاظتی رمزنگاری مشترک هستند.

بهبود ساختار جعبه های S یکی از مشکلات جدی است که در زمینه رمزهای بلوک متقارن مورد تحقیق قرار گرفته است. اساساً لازم است که هرگونه تغییر در ورودی جعبه های S به داخل آنها ریخته شود تصادفیبه ظاهر تغییر خروجی. از یک سو ، هرچه جعبه های S بزرگتر باشند ، الگوریتم در برابر روشهای رمزنگاری خطی و افتراقی مقاومت بیشتری دارد. از سوی دیگر ، طراحی یک میز جایگزین بزرگ دشوارتر است.

در الگوریتم های مدرن ، S-box ها معمولاً یک بردار (آرایه تک بعدی) هستند 2 اینچعناصر کمی ورودی بلوک تعداد عنصری را تعریف می کند که مقدار آن به عنوان خروجی بلوک S عمل می کند.

تعدادی از معیارها برای طراحی جعبه های S ارائه شده است. جدول جایگزینی باید دارای موارد زیر باشد:

• معیار دقیق سقوط بهمن ؛
• معیار استقلال بیت؛
• الزام غیر خطی از مقادیر ورودی.

برای تحقق آخرین الزام ، پیشنهاد شد یک ترکیب خطی مشخص شود منبیت ( من = 1, ..., T)مقادیر جدول جایگزینی توابع خم شده(انگلیسی ، خم شده -انحراف ، در این مورد - از توابع خطی). توابع خم شده کلاس خاصی از توابع بولی را تشکیل می دهند که با بالاترین طبقه غیر خطی و مطابقت با معیار سخت گیر بهمن مشخص می شود.

در بعضی از کارها ، برای جعبه های S ، پیشنهاد می شود که عملکرد بهمن تضمین شده سفارش y - هنگام تغییر یک بیت ورودی ، حداقل بیت های خروجی جعبه S را بررسی کنید. خاصیت اثر بهمن تضمین شده ی ترتیب y از 2 به 5 ویژگی های انتشار به اندازه کافی خوب جعبه های S را برای هر الگوریتم رمزگذاری فراهم می کند.

هنگام طراحی جداول جایگزین به اندازه کافی بزرگ ، می توان از رویکردهای زیر استفاده کرد:

• انتخاب تصادفی (برای جعبه های کوچک S ، می تواند منجر به ایجاد جداول جایگزینی ضعیف شود).
• انتخاب تصادفی به دنبال بررسی رعایت معیارهای مختلف و رد جعبه های S ضعیف ؛
• انتخاب دستی (برای بلوک های S بزرگ بسیار سخت است) ؛
• رویکرد ریاضی ، به عنوان مثال ، تولید با استفاده از توابع خم (این روش در الگوریتم CAST اعمال می شود).

روش زیر برای طراحی بلوک های S جداگانه از الگوریتم GOST 28147-89 قابل پیشنهاد است:

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

در سال 2011 ، یک حمله جدید "جلسه انعکاسی در وسط" پیشنهاد شد ، که مقاومت GOST 28147-89 (از 2256 به 2225) را کمی کاهش می دهد. بهترین نتیجه تجزیه و تحلیل رمزنگاری الگوریتم تا سال 2012 قدرت آن را به 2119 کاهش می دهد ، و به اندازه متن رمز نسبتاً بزرگ و حجم داده های از قبل تشکیل شده نیاز دارد. با وجود حملات پیشنهادی ، GOST 28147-89 در سطح فعلی توسعه فن آوری رایانه عملا پایدار است.

کد "ماگما" (GOST R 34.12-2015).استاندارد GOST 28147-89 بیش از 25 سال است که در روسیه اجرا می شود. در طول این مدت ، دوام کافی و کارایی خوبی از اجرای نرم افزار و سخت افزار ، از جمله در دستگاه های کم منبع ، نشان داده است. اگرچه حملات رمزنگاری ارائه شده است كه تخمین مقاومت آن را كاهش می دهد (بهترین مورد تا 2192 مورد است) ، اما عملی بودن آنها بسیار دور است. بنابراین ، تصمیم گرفته شد الگوریتم GOST 28147-89 در استاندارد رمزگذاری متقارن که به تازگی توسعه یافته است ، گنجانده شود.

در فروشگاه 2015 ، دو استاندارد جدید رمزنگاری ملی به تصویب رسید: GOST R 34.12-2015 «فناوری اطلاعات. محافظت از اطلاعات رمزنگاری رمزگذاری بلوک "و GOST R 34.13-2015" فناوری اطلاعات. محافظت از اطلاعات رمزنگاری نحوه عملکرد رمزهای بلوک "، که از تاریخ 1 ژانویه 2016 به اجرا در می آیند.

استاندارد GOST R 34.12-2015 شامل توصیف دو رمز بلوک با طول بلوک 128 و 64 بیت است. رمز GOST 28147-89 با بلوک های جایگزین غیرخطی ثابت در GOST R 34.12-2015 جدید به عنوان رمزگذاری 64 بیتی به نام "ماگما" گنجانده شده است.

در زیر بلوک های جایگزین ثابت شده در استاندارد آمده است:

مجموعه جعبه های S ارائه شده در استاندارد بهترین خصوصیاتی را ارائه می دهد که مقاومت الگوریتم رمزنگاری در برابر رمزنگاری دیفرانسیل و خطی را تعیین می کند.

طبق کمیته فنی استاندارد سازی "امنیت اطلاعات رمزنگاری" (TC 26) ، رفع بلوک های جایگزینی غیر خطی الگوریتم GOST 28147-89 را یکپارچه تر می کند و به از بین بردن استفاده از بلوک های جایگزینی غیر خطی "ضعیف" کمک می کند. علاوه بر این ، تثبیت در استاندارد همه پارامترهای طولانی مدت رمز با رویه بین المللی پذیرفته شده مطابقت دارد. استاندارد جدید GOST R 34.12-2015 از لحاظ اصطلاحی و مفهومی با استانداردهای بین المللی ISO / IEC 10116 «فناوری اطلاعات مرتبط است. روشهای امنیتی حالت های عملکرد برای "رمز بلوک بیت" (ISO / IEC 10116: 2006 فناوری اطلاعات - تکنیک های امنیتی - حالت های عملکرد برای رمز بلوک n -bit) و سری ISO / IEC 18033 "فناوری اطلاعات. روش ها و روش های اطمینان از ایمنی. الگوریتم های رمزگذاری ": ISO / IEC 18033-1: 2005" Part 1. General "(ISO / IEC 18033-1: 2005 فناوری اطلاعات - تکنیک های امنیتی - الگوریتم های رمزگذاری - قسمت 1: عمومی) و ISO / IEC 18033-3: 2010 "قسمت 3. رمزهای بلوک" (ISO / IEC 18033-3: 2010 (فناوری اطلاعات - تکنیک های امنیتی - الگوریتم های رمزگذاری - قسمت 3: رمزگذاری های بلوک)).

استاندارد GOST P 34.12-2015 همچنین شامل یک رمزگذاری بلوک جدید ("Grasshopper") با اندازه بلوک 128 بیت است. انتظار می رود این رمز در برابر تمام حملات رمزگذاری بلوک که امروزه شناخته می شوند ، مقاوم باشد.

روش های کارکردن رمزهای بلوک (جایگزینی ساده ، گاما ، گاما با بازخورد خروجی ، گاما با بازخورد متن رمز ، جایگزینی ساده با مشارکت و توسعه یک درج تقلیدی) در یک استاندارد جداگانه GOST R 34.13-2015 ، مطابق با رویه بین المللی پذیرفته شده این حالت ها هم برای رمز Magma و هم رمز جدید Grasshopper قابل استفاده هستند.

• تغییر دایره ای بیتی به سمت چپ 11 بیت انجام می شود. رمزگشایی مطابق با همان طرح انجام می شود ، اما با یک برنامه کلیدی متفاوت استفاده می شود: از مرحله 1 تا 8 رمزگشایی - به ترتیب مستقیم: از مرحله 9 تا 32 رمزگشایی - به ترتیب معکوس: در مقایسه با رمز DES در GOST 28147-89 از مزایای زیر برخوردار است: یک کلید به طور قابل توجهی طولانی تر (256 بیت در مقابل 56 برای رمز DES) ، حمله ای که با شمارش بی رحمانه مجموعه کلید در آن لحظه غیرممکن به نظر می رسد. یک برنامه ساده برای استفاده از کلید ، که اجرای الگوریتم را ساده و سرعت محاسبات را افزایش می دهد. طراحی بلوک های S GOST 28147-89. واضح است که طرح الگوریتم GOST 28147-89 بسیار ساده است. این بدان معنی است که بیشترین بار رمزگذاری روی جداول جایگزینی قرار می گیرد. مقادیر Tab
• الگوریتم های رمزگذاری Panasepko S.P.: یک کتاب مرجع ویژه. SPb.: BHV-Peter-burg ، 2009
• Kara O. حملات انعکاس به رمزگذاری محصولات. URL: http://eprint.iacr.org/2007/043.pdf
• استاندارد رمزگذاری روسی: کاهش قدرت. URL: http://cryptofaq.ru/index.php/2010-12-23-18-20-21/2010-12-23-18-22-09/90-2011-02-01-07-47- 27
• Achekseev E. K. ، Smyshlyaev S. V. GOST 28147-89: "برای دفن او عجله نکنید."

الگوریتم تعریف شده توسط GOST 28147-89 دارای طول رمزگذاری 256 بیت است. این اطلاعات را در بلوکهای 64 بیتی (این الگوریتمها را الگوریتمهای بلوک می نامند) رمزگذاری می کند ، سپس به دو ساب بلاک 32 بیتی (N1 و N2) تقسیم می شوند (شکل 1). ساب بلاک N1 به روشی خاص پردازش می شود ، پس از آن مقدار آن به مقدار ساب بلاک N2 اضافه می شود (اضافه شدن modulo 2 انجام می شود ، یعنی عملیات منطقی XOR - "اختصاصی یا" اعمال می شود) ، و سپس ساب بلاک ها عوض می شوند . این تغییر شکل تعداد مشخصی از دفعات انجام می شود ("دور"): 16 یا 32 ، بسته به نوع عملکرد الگوریتم. در هر دور ، دو عمل انجام می شود.

شکل 1. طرح الگوریتم GOST 28147-89.

اولین مورد همپوشانی کلید است. محتوای زیر بلوک N1 مدول 2 با قسمت 32 بیتی کلید Kx اضافه می شود. کلید رمزگذاری کامل به عنوان ترکیب زیر کلیدهای 32 بیتی نشان داده شده است: K0 ، K1 ، K2 ، K3 ، K4 ، K5 ، K6 ، K7. در فرآیند رمزگذاری ، بسته به تعداد دور و نحوه عملکرد الگوریتم ، از یکی از این کلیدهای فرعی استفاده می شود.

عملیات دوم تعویض میز است. پس از اعمال کلید ، زیر بلوک N1 به 8 قسمت 4 بیتی تقسیم می شود که مقدار هر یک مطابق با جدول جایگزینی این قسمت از زیر بلوک جایگزین می شود. سپس ، زیر بلوک به صورت بیتی با 11 بیت به چپ منتقل می شود.

جعبه های جایگزینی (جعبه های S) اغلب در الگوریتم های رمزگذاری مدرن استفاده می شوند ، بنابراین لازم است توضیح دهیم که چگونه چنین عملیاتی سازمان یافته است. مقادیر خروجی بلوک ها در جدول نوشته می شوند. یک بلوک از داده ها با یک بعد خاص (در مورد ما ، 4 بیتی) دارای نمایش عددی خاص خود است که تعداد مقدار خروجی را تعیین می کند. به عنوان مثال ، اگر جعبه S مانند 4 ، 11 ، 2 ، 14 ، 15 ، 0 ، 8 ، 13 ، 3 ، 12 ، 9 ، 7 ، 5 ، 10 ، 6 ، 1 و یک بلوک 4 بیتی "0100" باشد وارد ورودی شد (مقدار 4) ، سپس مطابق جدول ، مقدار خروجی 15 خواهد بود ، یعنی "1111" (0 a 4، 1 a 11، 2 a 2 ...).

الگوریتم تعریف شده توسط GOST 28147-89 ، چهار حالت عملیاتی را فراهم می کند: جایگزینی ساده ، درمان گاما ، تابش گامای بازخورد و تولید شبیه ساز. آنها از رمزنگاری یکسانی که در بالا توضیح داده شد استفاده می کنند ، اما از آنجا که هدف حالت ها متفاوت است ، این تغییر در هر یک از آنها به روش های مختلف انجام می شود.

در حالت جایگزینی ساده ، 32 دور توضیح داده شده در بالا برای رمزگذاری هر یک از اطلاعات 64 بیتی انجام می شود. در این حالت ، از کلیدهای فرعی 32 بیتی به ترتیب زیر استفاده می شود:

K0 ، K1 ، K2 ، K3 ، K4 ، K5 ، K6 ، K7 ، K0 ، K1 و غیره - در دورهای 1 تا 24 ؛

K7 ، K6 ، K5 ، K4 ، K3 ، K2 ، K1 ، K0 - در دورهای 25 تا 32.

رمزگشایی در این حالت به همان روش انجام می شود ، اما با توالی کمی متفاوت از استفاده از کلیدهای فرعی:

K0 ، K1 ، K2 ، K3 ، K4 ، K5 ، K6 ، K7 - در دور 1 تا 8 ؛

K7 ، K6 ، K5 ، K4 ، K3 ، K2 ، K1 ، K0 ، K7 ، K6 و غیره - در دورهای 9 تا 32.

همه بلوک ها به طور مستقل از یکدیگر رمزگذاری می شوند ، یعنی نتیجه رمزگذاری هر بلوک فقط به محتوای آن بستگی دارد (بلوک مربوط به متن منبع). اگر چندین متن یکسان از متن اصلی (ساده) وجود داشته باشد ، بلوک های متن رمز مربوطه نیز یکسان خواهند بود ، که اطلاعات مفیدی را برای رمزنگاری که سعی در شکستن رمز دارد ، می دهد. بنابراین ، این حالت عمدتا برای رمزگذاری کلیدهای رمزنگاری خود استفاده می شود (در اغلب موارد طرح های چند کلیده اجرا می شوند که در آنها ، به دلایلی ، کلیدها روی هم رمزگذاری می شوند). برای رمزگذاری خود اطلاعات ، دو حالت دیگر وجود دارد - بازی و بازی با بازخورد.

در حالت گاما ، هر بلوک متن ساده به صورت بیتی modulo 2 با یک بلوک گام رمزنگاری 64 بیتی اضافه می شود. گامای رمزنگاری یک توالی خاص است که در نتیجه عملیات خاصی با رجیسترهای N1 و N2 بدست می آید.

• 1. در ثبت N1 و N2 پر کردن اولیه آنها نوشته شده است - یک مقدار 64 بیتی ، synchro-burst نامیده می شود.
• 2. محتویات ثبت N1 و N2 در حالت جایگزینی ساده رمزگذاری می شوند (در این مورد ، پیام های همگام سازی).
• 3. محتویات ثبت N1 modulo (232 - 1) با ثابت C1 = 224 + 216 + 28 + 24 C1 اضافه می شود و نتیجه جمع به ثبت N1 نوشته می شود.
• 4- محتویات ثبت N2 مدول 232 با ثابت C2 = 224 + 216 + 28 + 1 1 ثابت اضافه می شود و نتیجه اضافه برای ثبت N2 نوشته می شود.
• 5- محتویات ثبات های N1 و N2 به عنوان یک بلاک 64 بیتی از گامای رمزگذار (در این حالت ، N1 و N2 اولین بلاگ گاما را تشکیل می دهند) خارج می شوند.

در صورت نیاز به بلوک بعدی گاما (یعنی باید رمزگذاری یا رمزگشایی را ادامه دهید) ، به مرحله 2 برمی گردید.

برای رمزگشایی ، گاما به روشی مشابه تولید می شود و سپس XOR به متن رمزگذاری شده و بیت های گاما دوباره اعمال می شود. از آنجا که این عملیات برگشت پذیر است ، در مورد مقیاس درست کار شده ، متن اصلی بدست می آید (جدول 1).

میز 1.رمزگذاری و رمزگشایی در حالت گاما

برای تولید گستره رمزگذاری مورد نیاز برای رمزگشایی ، کاربر رمزگشایی رمزنگاری باید همان کلید و همان پیام پیام همزمان را داشته باشد که برای رمزگذاری اطلاعات استفاده شده است. در غیر این صورت ، امکان دریافت متن اصلی از متن رمزگذاری شده وجود نخواهد داشت.

در اکثر پیاده سازی های الگوریتم GOST 28147-89 ، پیام همگام سازی مخفی نیست ، اما سیستم هایی وجود دارد که پیام همگام سازی همان عنصر مخفی کلید رمزگذاری است. برای چنین سیستم هایی ، طول موثر کلید الگوریتم (256 بیت) 64 بیت دیگر از پیام همگام سازی مخفی افزایش می یابد ، که می تواند به عنوان یک عنصر کلیدی نیز در نظر گرفته شود.

در حالت گاما بازخورد ، برای پر کردن ثبت های N1 و N2 ، از بلوک 2 شروع می شود ، نه بلوک گامای قبلی استفاده می شود ، بلکه نتیجه رمزگذاری بلوک متن ساده قبلی است (شکل 2). اولین بلوک در این حالت کاملاً مشابه حالت قبلی ایجاد می شود.

شکل 2. تولید گامای رمز در حالت گاما بازخورد.

با توجه به نحوه تولید شبیه سازها ، تعریف مفهوم موضوع تولید ضروری است. پیشوند یک جمع چک رمزگذاری شده است که با استفاده از یک کلید رمزگذاری برای تأیید صحت پیام ها محاسبه می شود. هنگام تولید پیشوند ، عملیات زیر انجام می شود: اولین بلوک 64 بیتی آرایه اطلاعات ، که پیشوند برای آن محاسبه می شود ، در رجیسترهای N1 و N2 نوشته شده و در حالت کاهش جایگزینی ساده رمزگذاری می شود (اولین 16 دور از 32 انجام می شود). نتیجه بدست آمده modulo 2 با بلوک بعدی اطلاعات خلاصه می شود و نتیجه را در N1 و N2 ذخیره می کند.

این چرخه تا آخرین بلوک اطلاعات تکرار می شود. محتوای 64 بیتی حاصل از ثبات های N1 و N2 یا بخشی از آن که در نتیجه این تغییرات بدست آمده است ، پیشوند نامیده می شود. اندازه پیشوند بر اساس قابلیت اطمینان پیام انتخاب می شود: با طول بیت های پیشوند r ، احتمال اینکه پیام تغییر نکند ، 2 r است. در بیشتر اوقات ، پیشوند 32 بیتی استفاده شده است ، یعنی نیمی از مطالب ثبت نام. این کافی است ، زیرا ، مانند هر بخش کنترل ، شبیه ساز در درجه اول برای محافظت در برابر تحریف تصادفی اطلاعات طراحی شده است. برای محافظت در برابر اصلاح عمدی داده ها ، از روش های رمزنگاری دیگری استفاده می شود - اول از همه ، یک امضای دیجیتال الکترونیکی.

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

الگوریتم GOST 28147-89 یک الگوریتم بسیار قوی تلقی می شود-در حال حاضر ، هیچ روش م effectiveثرتری برای افشای آن نسبت به روش "نیروی وحشیانه" فوق الذکر پیشنهاد نشده است. امنیت بالای آن در درجه اول به دلیل طول زیاد کلید - 256 بیت حاصل می شود. هنگام استفاده از یک پیام همگام سازی مخفی ، طول کلید موثر به 320 بیت افزایش می یابد ، و راز جدول جایگزینی بیت های اضافی را اضافه می کند. علاوه بر این ، قدرت رمزنگاری بستگی به تعداد دور تبدیل دارد ، که طبق GOST 28147-89 ، باید 32 مورد وجود داشته باشد (اثر کامل پراکندگی داده های ورودی پس از 8 دور حاصل می شود).

مزایای GOST 28147-89 وجود حفاظت در برابر تحمیل داده های کاذب (توسعه درج تقلید) و چرخه رمزگذاری یکسان در هر چهار الگوریتم GOST است.

DES یک استاندارد رمزگذاری داخلی است که برای اجرای نرم افزار راحت تر است.

برخلاف DES آمریکایی ، استاندارد روسیه از کلید طولانی تر - 256 بیت استفاده می کند. علاوه بر این ، استاندارد روسیه پیشنهاد می کند از 32 دور رمزگذاری استفاده کنید ، در حالی که DES - فقط 16.

بنابراین ، پارامترهای اصلی الگوریتم تبدیل داده های رمزنگاری GOST 28147-89 به شرح زیر است: اندازه بلوک 64 بیت ، اندازه کلید 256 بیت و تعداد دور 32 است.

این الگوریتم یک شبکه Feistel کلاسیک است. بلوک داده های رمزگذاری شده به دو قسمت یکسان تقسیم می شود ، R راست و چپ L. قسمت راست به کلید فرعی گرد اضافه می شود و قسمت چپ را با استفاده از برخی الگوریتم ها رمزگذاری می کند. قبل از دور بعدی ، دو طرف چپ و راست عوض می شوند. این ساختار امکان استفاده از یک الگوریتم یکسان برای رمزگذاری و رمزگشایی بلوک را فراهم می کند.

الگوریتم رمزگذاری از عملیات زیر استفاده می کند:

• افزودن کلمات modulo 2 32؛
• تغییر چرخشی کلمه به تعداد مشخص بیت ها به سمت چپ ؛
• مدول جمع بیتی 2؛
• جایگزینی مطابق جدول

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

ساختار گرد GOST 28147-89

ساختار یک دور GOST 28147-89 در شکل نشان داده شده است. 5.1

بلوک رمزگذاری شده داده به دو قسمت تقسیم می شود ، سپس به عنوان اعداد صحیح جداگانه 32 بیتی بدون علامت پردازش می شود. ابتدا نیمه راست بلوک و کلید فرعی دور modulo 2 32 اضافه می شوند. سپس تعویض بلوک به بلوک انجام می شود. مقدار 32 بیتی بدست آمده در مرحله قبل (بیایید آن را S بنامیم) به عنوان آرایه ای از هشت بلوک کد 4 بیتی تفسیر می شود: S = (S 0 ، S 1 ، S 2 ، S 3 ، S 4 ، S 5 ، S 6 ، S 7)... علاوه بر این ، مقدار هر یک از هشت بلوک با یک بلوک جدید جایگزین می شود ، که مطابق جدول جایگزینی به شرح زیر انتخاب شده است: مقدار بلوک S i به ترتیب با عنصر S i -th (شماره گذاری از صفر ) گره i-th جایگزینی ها (به عنوان مثال ، جدول های جایگزینی ردیف I ، که از صفر نیز شماره گذاری می شوند). به عبارت دیگر ، یک عنصر با یک شماره ردیف برابر با تعداد بلوک جایگزین شده و یک شماره ستون برابر با مقدار بلوک جایگزین شده به عنوان یک عدد صحیح غیر منفی 4 بیتی به عنوان جایگزینی برای مقدار بلوک انتخاب شده است. هر ردیف از جدول جایگزینی شامل اعداد 0 تا 15 به ترتیب تصادفی و بدون تکرار است. مقادیر عناصر جدول جایگزینی از 0 تا 15 گرفته می شود ، زیرا در چهار بیتی که جایگزین شده اند ، می توان یک عدد صحیح بدون علامت را در محدوده 0 تا 15 نوشت. به عنوان مثال ، خط اول جعبه S ممکن است حاوی مقادیری مانند این باشد: 5, 8, 1, 13, 10, 3, 4, 2, 14, 15, 12, 7, 6, 0, 9, 11 ... در این حالت ، مقدار بلاک S 0 (چهار بیت کم اهمیت تعداد 32 بیتی S) با عددی در موقعیتی که تعداد آن برابر با مقدار بلاک جایگزین شده است ، جایگزین می شود. اگر S 0 = 0 باشد ، 5 جایگزین می شود ، اگر S 0 = 1 ، 8 و غیره جایگزین می شود.

برنج. 5.1

پس از انجام تعویض ، تمام بلوک های 4 بیتی دوباره در یک کلمه 32 بیتی واحد ترکیب می شوند ، سپس به صورت چرخشی 11 بیت به سمت چپ منتقل می شود. سرانجام ، با عملیات bitwise "جمع حالت 2"نتیجه با نیمه چپ ترکیب می شود و در نتیجه نیمه راست جدید Ri ایجاد می شود. سمت چپ جدید L i برابر است با حداقل قسمت قابل توجهی از بلوک تبدیل شده: L i = R i-1.

مقدار حاصل از بلوک تبدیل شده در نتیجه یک دور الگوریتم رمزگذاری در نظر گرفته می شود.

روشهای رمزگذاری و رمزگشایی

بنابراین GOST 28147-89 یک رمزگذاری بلوک است تبدیل دادهانجام شده در بلوک به اصطلاح چرخه های پایه... حلقه های اصلی شامل چندین اجرا برای بلوک داده های دور اصلی است ، که ما قبلاً در نظر گرفتیم ، با استفاده از عناصر کلیدی مختلف و به ترتیب استفاده از عناصر اصلی با یکدیگر متفاوت هستند. هر دور از یکی از هشت کلید کلیدی 32 بیتی ممکن استفاده می کند.

بیایید روند ایجاد دورهای زیر کلید را در نظر بگیریم. در GOST ، این روش بسیار ساده است ، مخصوصاً وقتی با DES مقایسه شود. کلید 256 بیتی K به هشت زیر کلید 32 بیتی تقسیم می شود که K 0 ، K 1 ، K 2 ، K 3 ، ​​K 4 ، K 5 ، K 6 ، K 7 نشان داده می شود. این الگوریتم شامل 32 دور است ، بنابراین هر کلید فرعی برای رمزگذاری در چهار دور به ترتیب نشان داده شده در جدول 5.1 استفاده می شود.

جدول 5.1 ترتیب استفاده از کلیدهای فرعی برای رمزگذاری

گرد	1	2	3	4	5	6	7	8
ساخت کامل	K 0	K 1	K 2	K 3	K 4	K 5	K 6	K 7
گرد	9	10	11	12	13	14	15	16
ساخت کامل	K 0	K 1	K 2	K 3	K 4	K 5	K 6	K 7
گرد	17	18	19	20	21	22	23	24
ساخت کامل	K 0	K 1	K 2	K 3	K 4	K 5	K 6	K 7
گرد	25	26	27	28	29	30	31	32
ساخت کامل	K 7	K 6	K 5	K 4	K 3	K 2	K 1	K 0

فرآیند رمزگشایی از الگوریتم مشابه رمزگذاری پیروی می کند. تنها تفاوت در ترتیب استفاده از کلیدهای فرعی K i است. هنگام رمزگشایی ، باید از کلیدهای فرعی به ترتیب معکوس استفاده شود ، یعنی همانطور که در تصویر نشان داده شده است