zeyton

نمایی از عملکرد تابع F:


روش استخراج کليدهای فرعی از کليد اصلی:
استخراج کلیدهای فرعی (48 بیتی) از کلید اصلی (56 بیتی) روند ساده و سریعی دارد ولی روال ابهام آلود وسردرگم کننده آن به استحکام DES کمک شایانی کرده است.
روال تولید کلیدهای فرعی برگشت پذیر نیست (اصطلاحاً یکطرفه است) بدین معنا که با داشتن یک یا چند کلید فرعی نمی توان بصورت سر راست و مستقیم شاه کلید را پیدا کرد.


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

1) در اولین گام ،بیتهای کلید اصلی جایگشت داده می شوند. این جایگشت بیتی که اختصاراً PC-I = Permuted Choice one نامیده شده طبق جدول زیر انجام می گیرد.


2) در دومین گام، 56 بیت خروجی مرحله قبل در قالب دو نیمه 28بیتی با دو رجیستر با قابلیت شیفت چرخشی به سمت چپ وارد می شوند. تعداد شیفت ها در هر یک از مراحل 16 گانه تفاوت دارد و به شماره دور بستگی دارد. تعداد شيفت طبق جدول زير است:


3) در سومین گام از تولید کلید فرعی، خروجی شیفت یافته مرحله قبل، در قالب یک رشته بیتی 56 بیتی واحد ،مجدداً تحت جایگشت بیتی قرار می گیرد. این جایگشت بیتی که اختصاراً PC-2 Permuted Choice Two نامیده شده طبق جدول زیر انجام می گیرد. دقت کنید که در این جایگشت برخی از بیتهای ورودی در خروجی حضور ندارند زیرا باید از مجموع 56 بیت 48 بیت به عنوان کلید دور انتخاب شود.


برای تولید مابقی کلیدها همین روال از گام دوم تکرار می شود.

DESرمزگشایی:
یکی از زیبایی های DES آن است که عمل رمزگشایی داده ها نیاز به الگوریتم مجزا ندارد؛ هر گاه در الگوریتم رمز نگاری ترتیب کلیدها واژگون شود، رمزگشایی صورت خواهد گرفت به عبارت دیگر اگر در الگوريتم رمزنگاری بيت ها در کليدها را واژگون کنيم و بلوک رمز شده را به عنوان ورودی به الگوريتم اعمال کنيم، رمزگشايي صورت می گيرد.
رمز نگاری و رمز گشایی DES فرآیندی مستقل از جزئیات درونی تابع است. بدین معنا که می توانید در الگوریتم DES جزئیات تابع F را طبق میل خود تغییر بدهید و الگوریتم رمزنگاری و رمز گشایی مخصوص به خود را ایجاد کنید. روشن است که تابع F نقش بسیار پر اهمیتی در استحکام الگوریتم رمز نگاری ایفاء می کنید. این تابع باید بشدت غیر خطی و گمراه کننده باشد.

DESبررسی استحکام:
از زمانی که DES با پشتیبانی آژانس امنیت ملی آمریکا معرفی و به عنوان استاندارد فدرال توصیه شد، مناقشات و شایعات گسترده ای پیرامون آن در گرفت و شبهات زیادی به استحکام و امنیت آن وارد آمد.
در سال 1977 دو پروژه رمزنگاری از دانشگاه استنفورد به نام های «دیفی» و «هلمن»، طرح ماشینی برای شکستن رمز DES ارائه کردند و تخمین زدند این ماشین با هزینه ای حدود 20 میلیون دلار قابل ساخت است. این ماشین می توانست با داشتن یک قطعه کوچک از متن اصلی و کل متن رمز شده، کلید رمز را بین 256 حالت مختلف، در کمتر از یک روز پیدا کند. آن سالها کسی چنین پولی را نداد و چنین ماشینی هرگز ساخته نشد تا شایعه ضعف DES باقی بماند! حدود 20 سال بعد با ارزانتر شدن تکنولوژی و فراگیر شدن اینترنتت، رمز شکنی DES (به روش جستجوی کلید) میسر شد. با ارزان تر شدن پردازنده ها، ماشین های چند پردازنده متعددی برای شکستن DES طراحی و گاه ساخته شدند.
به هر حال شایعات و اتهامات هیچ گاه از دامان DES پاک نشدند و تلاش IBM نیز برای قدرتمندتر کردن آن با معرفی DES ـ 3 کمک چندانی به محبوبیت آن نکرد و سرانجام با معرفی روش AES تیر خلاص به DES زده شد.

طبیعت الگوریتم DES:
پيچيدگی DES از «به شدت غير خطي» بودن جداول جانشينی و غير قابل بازگشت بودن تابع F در صورت در اختيار نداشتن کليد k ، ناشی شده است.
آنچه که در خصوص معيارهای انتخاب S-Box های هشت گانه آشکار شده، آن است که:
1) خطی نبودن رابطه بين بيت های خروجی
2) هر سطر از جدول نگاشت S-Box ها تمام 16 حالت مختلف 0 تا 15 را در بر می گيرد تا فضای حالت خروجی دقيقا 16 باشد.
3) هرگاه دو ورودی 6 بيتی از يک S-Box واحد ، تنها در يک بيت تفاوت داشته باشد، خروجی آنها حداقل در دو بيت اختلاف دارد.
4) هرگاه دو ورودی به S-Box واحد در دو بيت ابتدايي اختلاف داشته باشند و در دو بيت انتهايي مشابه باشند، خروجی يکسان حاصل نمی شود.
شرایط فوق معیارهایی هستند که رمز شکن ها را متقاعد می سازد که S-BOX ها به شدت غیر خطی هستند و این الگوریتم از سطح گمراه کنندگی بالایی برخوردار است.

DES ـ 3
الگوریتم رمزنگاری DES ـ 3 (Triple DES)، روش مستقل و جدیدی به شمار نمی آید بلکه حاصل تلاش IBM برای افزایش موثر طول کلید و ایجاد اطمینان بیشتراست. در الگوریتم DES- 3 داده ها به کمک دو کلید 56 بیتی سه بار رمزنگاری می شوند. بنابراین فضای حالت کلید از 256 به112 افزایش می یابد که طول قابل قبولی است و دست هیچ یک از ماشینهای رمز شکن به چنین فضای بیکرانی نخواهد رسید.
در روش DES ـ 3 بلوک 64 بیتی ورودی ابتدا با کلید K1 رمزنگاری می شود. سپس حاصل این مرحله با کلید K2 رمزگشایی می شود. (رمزگشایی با کلید K2 هیچ تفاوتی با رمزنگاری ندارد.) سپس بار دیگر حاصل با کلید K1 رمز نگاری خواهد شد تا نتیجه رمز شده در خروجی بدست آید.


در اينجا از دو مرحله رمزنگاری و يک مرحله رمزگشايي برای رمزنگاری استفاده می شود. دليل رمزگشايي در مرحله دوم آن است که هرگاه کليدهای K1 و K2 مثل هم انتخاب شوند، دو بلوک اول تاثير يکديگر را خنثی می کنند و 3-DES به DES تبديل خواهد شد.

__________________

zeyton

در این پست پیاده سازی des رو با استفاده از نرم افزار matlab به همراه تمام جداول موردنیاز گذاشتم. امیدوارم به دردتون بخوره...

فايل ضميمه

DES_code.zip (163.8 كيلو بايت, 110 نمايش)

__________________

zeyton

رمزنگاری AES:
DES قربانی حمایت دولت فدرال آمریکا شد. NIST نخواست که تجربه ناموفق DES را تکرار کند. بنابراین رقابتی چند مرحله ای از ژانویه 1977 تا نوامبر 2001 ترتیب داد تا استاندارد جدیدی برای رمزنگاری از بین روش هایی که توسط شخصیتهای حقیقی پیشنهاد شده اند، انتخاب شود و هر گونه شائبه دخالت در فرآیند طراحی و وجود (Backdoor) را از بین ببرد.
پس از طی مراحل چندگانه این رقابت:
دو جوان بلژیکی Rijmen و Daemen پیروز این رقابت شدند.
الگوریتم این دو توسط NIST استاندارد سازی و در سند FIPS 197 تحت نام AES (Advanced Encryption Standard ) عرضه شد. این الگوریتم در ابتدا Rijndael نامیده شد. این روش نه تنها DES را که الگوریتمهای دیگری مثل RC4 را نیز به حاشیه رانده است.

دلایل شگفتی سازی روش رمزنگاری Rijndael در دنیای رمزنگاری کلید متقارن :

1) عدم پیروی این روش از الگوی سنتی روشهای فیستلی و مبتنی بر حالت خاصی از «میدان های گالوا» (Galios Field ) می باشد.
2) انتخاب این روش بعنوان استاندارد دولت فدرال آمریکا در فضائی آزاد و بدون اعمال نفوذ عوامل جاسوسی یا امنیتی ایالات متحده و ثبت تحت قوانین غیر انحصاری و لذا بهره برداری آزاد از آن در محصولات مختلف
3) امنیت بسیار بالا، سرعت زیاد، پیاده سازی ساده، فضای حافظه مورد نیاز کم و قابلیت انعطاف بالا

اختلاف بين Rijndael و AES :

1) در Rijndael، طول کلید و طول بلوک داده می تواند 128، 192 و 256 بیت باشند لذا می توان گفت که Rijndael دارای 9 انتخاب متفاوت برای رمزنگاری اطلاعات است.
2) در AES طول بلوک داده صرفاً باید 128 بیتی (معادل 4 کلمه 32 بیتی) باشد ولی طول کلید را از بین یکی از مقادیر 128، 192 و 256 بیتی انتخاب می کنند بدین ترتیب AES کلاً دارای سه انتخاب است.
این پارامترها باید به الگوریتم رمزنگاری وارد شوند:
Nb: طول بلوک داده ورودی (در AES هميشه 4 است.)
Nk: طول کليد (4 ، 6 يا 8)
Nr : تعداد دورهای رمزنگاری( به طول کليد وابسته است)


بلوک داده و کليد طبق الگوی شکل زير در ماتريسی با 4 سطر ذخيره می شود و عمليات پردازش بر روی ستون های 4 بايتی انجام می گيرد.


بررسی شبه کد AES برای حالت خاص AES-128:


تابع رمزنگار rijndael دارای 3 آرگومان است:
1) plaintext: آرايه ای به طول 16بايت حاوی داده های رمز نشده اصلی
2) Ciphertext: آرايه ای به طول 16 بايت برای برگرداندن معادل رمزنگاری شده ی داده های ورودی
3) Key : آرايه ای به طول 16 بايت حاوی کليد رمزنگاری
متغير دو بعدی state يک آرايه 4*4 است که داده های ورودی درون آن منتقل و پردازش ها بر روی آن انجام می گیرد. (متغير حالت)
متغير سه بعدی rk دارای 11 عنصر است، که هر عنصر يک کليد است. هر عنصر آن خود یک ماتریس 4×4 است بنابراین rk[0] تا rk[10] همگی ماتریس هائی هستند که باید در هر دور از برنامه با «متغیر حالت» XOR شوند.
فقط یک شاه کلید 16 بایتی وجود دارد مابقی ده کلید فرعی، طبق الگوریتم نسبتاً پیچیده ای از روی شاه کلید اصلی تولید می شود.

اولین اختلاف AES با DES:
DESبر روی بیت ها کار می کند و AES بر روی کلمات 32 بیتی

متغیر سه بعدی rk:


1) در ابتدای برنامه با فراخوانی تابع() expand-key، شاه کلید (یعنی متغیر key) به یازده کلید فرعی، توسعه داده می شود و درون متغیر rk قرار می گیرد تا در برنامه از آنها استفاده شود.
2) در مرحله بعدی ،متن اصلی به درون آرایه state منتقل می شود تا در ده دور متوالی پردازش شود. عمل کپی داده ها به درون آرایه state باید به صورت ستونی انجام گیرد: یعنی چهار بایت اول در ستون اول، چهار بایت دوم در ستون دوم و...... شماره گذاری سطر ها و ستونها از صفر آغاز می شود.
3) قبل از شروع حلقه تکرار،rk[0] با آرایه state، بایت به بایت XOR می شود.

__________________

zeyton

در الگوریتم DES حلقه تکرار ده دور محاسبات رمز نگار را انجام می دهد. هر دور شامل چهار عمل است:

1) Substitute:
این تابع یکایک بایتهای ماتریس state را بر اساس یک جدول جانشینی ثابت و مشخص با مقادیر جدید جایگزین می کند. جدول جانشینی بایت در AES دارای 256 درایه (Entry) است که در یک ماتریس 16×16 سازماندهی شده اند. برای جایگزین کردن بایت با مقدار معادل، چهار بیت پر ارزش آن بایت به عنوان شماره سطر و چهار بیت کم ارزش به عنوان شماره ستون به این جدول اعمال شده و درایه متناظر با آن بجای مقدار اصلی قرار می گیرد. برخلاف DES که دارای 8 جدول جانشینی برای هر دور است، AES در این مرحله فقط یک جدول BOX ـ S بیشتر ندارد (نقطه قوت این الگوریتم: نیاز به حافظه نوع ROM را در پیاده سازی سخت افزاری آن کاهش خواهد داد.) تمام بایتهای متغیر state طبق همین الگو با مقدار معادل، جایگزین می شوند.


2) rotate-rows:
این تابع هر چهار سطر از آرایه state را به سمت چپ می چرخاند؛ سطر شماره صفر، صفر بایت می چرخد ، سطر شماره 1، یک بایت بصورت چرخشی به سمت چپ می چرخد. سطر شماره 2، دو بایت و سطر شماره 3، سه بایت. در این گام جای بایتهای داده تغییر می کند.


3)mix_columns:
این تابع هر ستون از آرایه state را بطور مستقل از دیگر ستون ها تلفیق و در هم سازی می کند. هر ستون از state، در یک ماتریس ثابت ضرب می شود تا ستون جدید بدست آید؛ عمل ضرب ماتریسی، بر روی میدان GF که یک میدان محدود گالوا است، صورت می گیرد.


آنچه که AES را از دیگر روشهای موجود متمایز ساخته است زیر بنای ریاضی «عملیات تلفیق و در هم سازی» است.
در چهارمین مرحله و آخرین مرحله هر دور «کلید فرعی متناسب با آن دور» با داده ها XOR خواهد شد.

4) xor_roundkey_into_state:
این تابع محتویات متغیر state را با محتویات کلید متناظر با دور (یعنیrk[r] ) بایت به بایت XOR می کند.


در دورهای بعدی این چهار عمل متوالیاً بر روی محتویات ماتریس state انجام می گیرد.
پس از انجام تمام دورهای پردازش، کل عملیات رمزنگاری بلوک داده 128 بیتی به پایان می رسد و حاصل رمزنگاری داده ها که درون متغیر state قرار دارد به متغیر ciphertext منتقل میشود.
عمل تلفیق و درهم سازی ستونی استثناء در دور آخر انجام نمی شود تا الگوریتم حالت تقارن خود را حفظ کرده و رمزگشایی آن به راحتی ممکن باشد.

__________________

zeyton

توسيع کليد در AES:
تعداد کليدهای فرعی مورد نياز، به تعداد دورها(Nr) و تعداد دورها نيز به کليد(Nk) وابسته است.
در AES تنها یک (Master key) وجود دارد که کلیه «کلید های دور» (Round key)، طبق یک الگوریتم پیچیده وارون ناپذیر از روی آن ساخته می شود.
در 128 ـ AES طول کلید 128 بیت و تعداد دورها ده تا است لذا باید ده کلید فرعی دیگر از روی شاه کلید ساخته شود.

1) برای تولید اولین کلید فرعی، «شاه کلید» در ستون صفر تا 3 از یک ماتریس (به ابعاد 4 سطر و 44 ستون) قرار می گیرد.

2) ستون چهارم از کلید (یعنی ستون با اندیس 3) را به درون یک آرایه 4×1 منتقل کرده و در اولین گام، به آن یک شیفت چرخشی از پائین به بالا می دهیم. پس از این چرخش یکایک بایتهای ستون طبق یک جدول جانشینی ثابت با مقادیر جدید جایگزین می شوند.

3) پس از عمل جانشینی بایت ها، ستون جدید با ستون اول (ستون شماره صفر) از کلید اصلی XOR می شود.

4) XORمجدد آن با ستون متناظر از جدولی ثابت به نامRcon(round constant) انجام می شود. ستون متناظر از این جدول عبارتست از شماره ستون فعلی (که در حال ساخت آن هستیم یعنی ستون شماره 4) تقسیم بر NK، که در این مرحله برابر [1] Rcon می شود.

5) ستون اول از کلید فرعی حاضر است. سه ستون بعدی راحت تر بدست می آیند: ستون اول از کلید جدید با ستون دوم از کلید قبلی، XOR شده و ستون دوم از کلید جدید را می سازند. ستون جدید مجدداً با ستون سوم از کلید قدیم باز هم XOR شده و ستون سوم از کلید جدید را می سازد. بدین ترتیب چهار ستون از کلید فرعی اول محاسبه می شود.

6) برای محاسبه دومین کلید فرعی کافی است کلید محاسبه شده قبلی را کلید اصلی فرض کرده و همین روال تکرار تا کلید دوم بدست آید.

این روال تا تولید تمام کلیدهای مورد نیاز تکرار می شود.

يک مثال از توسيع کليد:

__________________

zeyton

پيش زمينه های رياضی در رمزنگاری AES:

گروه:
گروه تشکيل شده ازيک مجموعه مثل G که به همراه عملگرفرضی ⨁ بصورت (G, ⨁) نشان داده می شود و دارای خواص زير است:
1) اين عملگر روی مجموعه G بسته است.
2) اين عملگر دارای خصوصيت شرکت پذيری است.
3) اين عملگر بايد دارای عضو همانی باشد.
4) به ازای هر عنصر مثل a از G ، يک عنصر معکوسa متعلق به G وجود داشته باشد.

گروه آبلی (Abelian Group) يا گروه جابجايي: علاوه بر شرايط گروه شرايط زير را دارا باشد: a,b ∈G ⇒a⨁b=b⨁a∀

گروه محدود (Finite Group): تعداد عناصر G محدود و قابل شمارش باشد. برای گروه های محدود، نماد Ord(G) تعداد عناصر گروه را مشخص می کند.

گروه چرخه ای: هرگاه يک مؤلفه مثل a درG پيدا شود به نحوی که توانهای متوالی آن به شکل a^i ، تمام عناصر G را توليد کند.

قضيه لاگرانژ: Ord(H) | Ord(G)
يعنی تعداد عناصر H ، تعداد عناصر G را می شمارد.

حلقه:
يک حلقه تشکيل شده از يک مجموعه به نام R که دو عملگر فرضی ⨂و⨁ بر روی آن تعريف و با نماد (R,⨁,⨂) معرفی می شود.با شرايط زير:
1) (R,⨁) بايد يک گروه آبلی باشد.
2) Rبر روی عملگر دوم بايد دارای خواص شرکت پذيری باشد.
3) عملگر دوم بر روی عملگر اول بايد دارای خصوصيت پخشی از چپ به راست باشد.
4) عملگر دوم نيز بايد به ازای تمام عناصر R ، دارای عضو همانی در همين مجموعه باشد.

ميدان:
هرگاه مجموعه F به همراه دو عملگر فرضی يک حلقه جابجايی باشد و در عين حال هر عضو F بر روی عملگر دوم نيز معکوس داشته باشد.

میدان محدود: تعداد عناصر میدان F محدود و قابل شمارش باشد Ord(F) تعداد عناصر میدان است.
اگر P عددی اول باشد Zp اعداد غیر صفر کمتر از p باشد عملگر ضرب پیمانه ای و مجموعه Zp یک گروه آبلی می باشد.

چند جمله های روی Zp: مجموعه Zp (باقيمانده اعداد به پيمانه P) با دو عملگر جمع و ضرب پيمانه ای يک ميدان محدود را تشکيل خواهد داد. جمع دو چندجمله ای عبارت خواهد بود از جمع ضرايب جملات هم توان به پيمانه p و ضرب چندجمله ها نيز به پيمانه p انجام می گيرد يعنی پس از محاسبه ضرايب ، نتيجه به پيمانه P کاهش مي يابد.

ميدان گالوا GF(p) : مجموعه Zp به همراه دو عملگر جمع و ضرب پيمانه ای (p) يک ميدان محدود را تشکيل می دهند، که به آن ميدان گالوای GF(p) می گويند.

__________________

zeyton

توصيف رياضی روش AES:
کوچکترين واحد اطلاعات در الگوريتم AES يک بايت است. نمايش رياضی آن در ميدان GF(2) بصورت زير است:
پياده سازی عمل جمع دو بايت که در ميدان GF(2) مدل شده اند، همان عمل xor است.

میدان گالوای GF(2):
مجموعه Z2 یعنی{1،0} به همراه عملگرهای جمع و ضرب پیمانه ای به پیمانه 2 یک میدان محدود است.
چندجمله ایهای روی این میدان خود یک حلقه را تشکیل می دهند. ضرایب هر جمله یا صفر یا یک است ومحاسبات در پیمانه 2 می باشد.
یکی از کاربردهای آن در CRC میباشد.

جمع بایتها:

ضرب بایتها:
حال باید حاصلضرب را به پیمانه m(x) کاهش داد تا در هشت بیت قابل نمایش باشد:
مجموعه چند جمله ايها با دو عملگر xor و «ضرب پيمانه ای به پيمانه m(x) » يک ميدان را تشکيل می دهد.

تبدیل Mix Columens در رمزنگاری AES:
این تابع هر ستون از آرایه State را به طور مستقل از دیگر ستون ها، تلفیق و درهم سازی می کند. عمل تلفیق به این نحو است که هر ستون در یک ماتریس ثابت ضرب می شود تا ستون جدید بدست آید.


درجه ستونی مانریس ثابت حداکثر 3 می باشد.

الگوریتم رمزگشایی AES:
الگوریتم رمزگشایی AES فقط در ثابت ها و کلید های دور با الگوریتم رمزگذاری تفاوت دارد.


تفاوت های الگوریتم رمز گشای AES با رمز گذار آن:
1) وارون عمل AddRoundKey (یا همان XOR) تکرار آن است. زیرا:
2) برای عمل وارون جانشینی بایت ها، کافی است جدول جانشینی با مقادیر مناسب پر شود و از لحاظ ماهیت پیاده سازی تفاوتی ندارد.
3) وارون عمل شیفت چرخشی، باز هم شیفت چرخشی است.
4) برای وارون سازی MixColumens کافی است همین عمل با مقادیر «ماتریس وارون» یا a^-1 از نو تکرار شود. پس برای رمز گشایی AES فقط باید در ثابت های الگوریتم تغییر داد، نه در ماهیت عمل.

تصویری از پیاده سازی سخت افزاری AES:

__________________

sahar_gtc

سلام
وقتتون بخیر
من دارم روی s-box الگوریتم aes مطالعه میکنم..ممنونم میشم اگه کد این قسمت و تو متلب یا زبانهای دیگه دارید برام ارسال کنید .
مرسی وقت میزارید.
sahar_gtc3146@yahoo.com
ممنون میشم به این آدرس ارسال نمایید.
با تشکرو احترام

امین 58

سلام دوست عزیز . تشکر بابت مطلب مفیدتون.
موضوع پایان نامه من درمورد خطی بودن و غیر خطی بودن و یکنواختی دیفرانسیل در توابع دوری در رمزنگاری s-boxes هست .
تشکر میکنم اگر منبع مقاله یا کتاب برام معرفی کنین .