معرفی و بررسی روش رمزنگاری AES
چکیده
در این گزارش الگوریتم رمزنگاری Rijndael که در حال حاضر بعنوان استاندارد رمز نگاری پیشرفته یا
(Advanced Encryption Standard(AES شناخته می شود ، بررسی خواهد شد. ابتدا تاریخچه ای کوتاه از این الگوریتم بیان می شود و سپس به بررسی پیش نیاز های ریاضیاتی برای درک بهتر این الگوریتم و سپس به گام های مختلفی که برای ایجاد برنامه رمزنگار طی شده است ، پرداخته خواهد شد.
1. تاریخچه و معرفی AES :
AES به عنوان یک مشخصه برای رمزنگاری داده های دیجیتال است که توسط دولت ایالات متحده اتخاذ شده است و امروزه بصورت جهانی استفاده می شود.AES جانشین DES می باشد. الگوریتمی که توسط AES توصیف می شود ، یک الگوریتم کلید متقارن است. به این معنا که از یک کلید مشابه برای رمز کردن و گشودن اطلاعات استفاده می شود.
AES در تاریخ 26 نوامبر 2001 و پس از پنج سال فرایند استاندارد سازی که رقابتی بین 15 طراحی مختلف بود، توسط بنیاد ملی استانداردها و فناوری NIST با عنوان U.S FIPS PUB 197(FIPS 197) معرفی شد.AES اولین رمزنگار رمز باز و قابل دسترس برای عموم است که توسط آژانس امنیت ملی NSA برای اطلاعات فوق محرمانه پذیرفته شد .
نام آن Rijndael می باشد و توسط دو رمزنویس بلژیکی با نام های Joan Daemen و Vincent Rijmen توسعه یافته و به انتخابات AES معرفی شده است. Rijndael با تلفظ [ˈrɛindaːl] تلفیقی از نام مخترعانش می باشد.
اگر بخواهیم دقیق شویم می توان گفت که AES نام استاندارد است و الگوریتم توصیف شده گونه ای از Rijndael است.
2.مقدمات ریاضی:
چندین عملیات در Rijndael در سطح بایت، با بایتهایی که عناصر میدان متناهی GF(28) را نشان می دهند، توصیف می شوند. عملیات های دیگر در بیان هایی از کلمات 4 بایتی تعریف می شوند. در این قسمت به معرفی مفاهیم ریاضیاتی پایه ای که برای ادامه گزارش نیاز هستند پرداخته می شود.
1.2 میدان (GF(28
عناصر یک میدان متناهی یا finite field با روش های گوناگونی قابل بیان هستند. برای هر توان اول یک میدان متناهی تک وجود دارد ، از این رو تمام نمایش های (GF(28 متناظر هستند. با وجود این هم ارزی ، نحوه نمایش بر پیچیدگی های پیاده سازی ،اثرگذار خواهد بود. ما از نمایش چند جمله ای های کلاسیک استفاده می کنیم.
اگر b را یک بایت فرض کنیم که شامل b7 b6 b5 b4 b3 b2 b1 می باشد، بوسیله یک چند جمله ای با ضرایب {0, 1} در نظر گرفته می شود :
b7 x7 +b6 x6 +b5 x5+b4 x4 +b3 x3 +b2 x2 +b1 x +b0
مثال :
یک بایت با مقدار هگزادسیمال "57" (باینری 01010111) مرتبط به چند جمله ای زیر است :
x6 + x4 + x2 + x + 1
1.1.2 جمع
در نمایش چند جمله ای ، مجموع دو عنصر ، برابر چند جمله ای با ضرایبی است که با جمع ضرایب دو عبارت در پیمانه 2 بیان می شود ( یعنی 1+1=0 ).
مثال :
‘57’ + ‘83’ = ‘D4’ یا به بیان چند جمله ای ها :
)x6 + x4 + x2 + x + 1( + (x7 + x +1 ) = x7 + x6 + x4 + x2
در نشان گذاری دودویی داریم “01010111” + “10000011” = “11010100”
بوضوح مشخص است که عمل جمع، متانظر با عمل XOR بیتی در سطح بایتی است.
تمامی شرایط ضروری برای داشتن یک گروه آبلی براورده شده است : شرکت پذیری، بسته بودن ، عنصر خنثی (‘00’) ، عنصر معکوس(هر عنصر معکوس جمعی خودش است) و جابجایی پذیری. با توجه به اینکه هر عنصر معکوس جمعی خودش است ، عمل جمع و عمل تفریق یکسان هستند.
2.1.2 ضرب
در نمایش چند جمله ای ، عمل ضرب در GF(28) مشابه با ضرب چند جمله ای ها در پیمانه ی یک چند جمله ای تجزیه ناپذیر با درجه 8 است. یک چند جمله ای تجزیه نا پذیر است اگر هیچ مقسوم علیهی بجز 1 و خودش نداشته باشد. برای Rijndael این چندجمله ای m(x) نامیده شده و به این صورت داده می شود :
M(x) = x8 + x4 + x3 + x + 1
یا ‘11B’ در نمایش هگزادسیمال.
مثال :
‘57’ · ‘83’ = ‘C1’ یا
(x6 + x4 + x2 + x + 1) ( x7 + x + 1) = x13 + x11 + x9 + x8 + x7 +
x7 + x5 + x3 + x2 + x +
x6 + x4 + x2 + x + 1
= x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1
x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1 modulo x8 + x4 + x3 + x + 1
= x7 + x6 + 1
مشخص است که نتیجه ، یک چند جمله ای دودویی از درجه کمتر از 8 است . بر خلاف عمل جمع ، عملیات ساده ای در سطح بایتی نیست.
عمل ضرب معرفی شده در بالا ، شرکت پذیر است و دارای عنصر خنثی (‘01’) است. برای هر چند جمله ای دودویی b(x) از درجه کمتر از 8 ، الگوریتم گسترش یافته اقلیدس برای محاسبه چند جمله ای های a(x) و c(x) استفاده می شود بطوری که :
b(x )a(x ) + m(x )c(x ) = 1
از این رو a(x ) · b(x ) mod m(x )= 1 یا
b-1(x ) = a(x ) mod m(x )
علاوه بر این ، نشان می دهد که
a(x ) · (b(x ) + c(x )) = a(x ) · b(x ) + a(x ) · c(x )
این نشان دهنده اینست که مجموعه ای از 256 مقدار بایت ممکن ، با XOR بعنوان جمع و ضرب تعیین شده در بالا دارای ساختاری از میدان متناهی GF(28) است.
3.1.2 ضرب در x
اگر b(x) در چند جمله ای x ضرب شود ، حاصل بصورت زیر خواهد بود :
b7 x8 + b6 x7 + b5 x6 + b4 x5 + b3 x4 + b2 x3 + b1 x2 + b0 x
حاصل x · b(x) بوسیله کاهش نتیجه فوق در پیمانه m(x) بدست خواهد آمد.اگر b7 = 0 ، این کاهش ، یک عملیات همانی خواهد بود، اگر b7 = 1 ، m(x) باید تفریق شود( یا بعبارت دیگر XOR شود). این یعنی اینکه ضرب در x (با مقدار هگزا دسیمال 02 ) بوسیله یک شیفت به چپ و XOR بیتی شرطی بعد از آن با ‘1B’ در سطح بایتی انجام می شود.این عمل بصورت زیر بیان می شود.
b = xtime(a).
ضرب با توانی بالا تر از x را می توان با تکرار عملیات xtime انجام داد. با اعمال نتایج میانی ،عملیات ضرب در هر مقدار ثابتی قابل انجام است.
مثال :
‘57’ · ‘13’ = ‘FE’
‘57’ · ‘02’ = xtime(57) = ‘AE’
‘57’ · ‘04’ = xtime(AE) = ‘47’
‘57’ · ‘08’ = xtime(47) = ‘8E’
‘57’ · ‘10’ = xtime(8E) = ‘07’
‘57’ · ‘13’ = ‘57’ · (‘01’ ⊕ ‘02’ ⊕ ‘10’ ) = ‘57’ ⊕ ‘AE’ ⊕ ‘07’ = ‘FE’
2.2چندجمله ای ها با ضرایبی در (GF(28
می توان چند جمله ای ها را با ضرایبی در GF(28) تعریف کرد. در این روش ، یک بردار 4 بایتی که مشابه چند جمله ای از درجه کمتر از 4 است. چند جمله ای ها را می توان با جمع ساده ضرایبشان ، با هم جمع کرد.با توجه به اینکه در GF(28) عمل ضرب ، عمل XOR بیتی است، جمع دو بردار ، یک XOR بیتی ساده است. ضرب کردن عمل پیچیده تری است ، فرض می کنیم که دو چند جمله ای روی GF(28) داریم :
a(x ) = a3 x3 + a2 x2 + a1 x + a0 and b(x ) = b3 x3 + b2 x2 + b1 x + b0
حاصل ضرب c(x ) = a(x )b(x ) بصورت زیر خواهد بود
c(x ) = c6 x6 + c5 x5 + c4 x4 + c3 x3 + c2 x2 + c1 x + c0
که در آن :
مشخص است که دیگر c(x) نمی توان را با یک بردار 4 بایتی نشان داد. با کاهش c(x) به پیمانه یک چند جمله ای از درجه 4 ، می توان نتیجه را به یک چند جمله ای از درجه کمتر از 4 کاهش داد. در Rijndael این امر با استفاده از M(x)=x4+1 انجام می شود . به این صورت :
xi mod x4+1=xi mod 4
حاصلضرب پیمانه ای (a(x و (b(x ، که با
نشان داده می شود به این صورت انجام می شود
d(x ) = d3 x3 + d2 x2 + d1 x + d0
که در آن
عملیلات شامل ضرب با چند جمله ای ثابت( a(x می تواند بصورت ضرب ماتریسی نوشته شود که ماتریس در آن یک ماتریس چرخشی (دوری) است. داریم :
= 
توجه : x4 + 1 یک چند جمله ای تجزیه ناپذیر روی (GF(28 نیست. پس ضرب با یک چند جمله ای ثابت لزوما معکوس پذیر نیست. در الگوریتم Rijndael از یک چندجمله ای ثابت که دارای معکوس باشد استفاده می شود.
1.2.2 ضرب در x
اگر b(x) را در x ضرب کنیم ، خواهیم داشت :
b3x4+b2x3+b1x2+b0x
حاصل 
بوسیله کاهش نتیجه فوق با 1+ x4 بدست می آید.که نتیجه بصورت زیر خواهد بود :
b2x3+b1x2+b0x+b3
ضرب کردن در x متناظر با ضرب کردن یک ماتریس مانند بالا است که در آن همه ai=’00’ است بجز a1=’01’ . اگر
خواهیم داشت :
در نتیجه ضرب در x ،یا توان x ، مشابه است با یک شیفت دوره ی در بایت های درون بردار.
3. اساس طراحی
سه معیار ی که هنگام طراحی Rijndael در نظر گرفته شده اند از این قرارند
· مقاومت در برابر تمامی حملات شناخته شده.
· سرعت و فشردگی کد در یک رنج وسیع از پلتفرم ها
· سادگی طراحی
در اکثر الگوریتم های رمزنگاری ، تبدیل راند (round transformation) دارای ساختار فیستل(Feistel) می باشند. در این ساختار قسمت های نوعی از بیت ها در حالت های میانی ، بدون تغییر به موقعیتی دیگر منتقل می شوند.
تبدیل راند در Rijndael دارای ساختار Feistel نیست. در عوض، تبدیل راند ترکیبی از سه تبدیل یکنواخت معکوس پذیر است که لایه نامیده می شوند. منظور از یکنواخت اینست که هر بیت حالت، مانند هم رفتار می کنند.
انتخاب های ویژه برای لایه های مختلف برای قسمت بزرگی هستند که بر اساس کاربرد های استراتژی دنباله وسیع (Wide Trail Strategy)است ، که یک روش طراحی برای فراهم کردن مقاومت در برابر رمزشکنی های تفاضلی(differential cryptanalysis) است. در Wide Trail Strategy ، هر لایه ،کاربرد خودش را دارد.
لایه ترکیب خطی : انتشار زیاد در راندهای چندتایی را تضمین می کند.
لایه غیرخطی : کاربردهای موازی S-box ها که خاصیت های غیر خطی در بدترین موارد
را بهینه می کند.
لایه افزودن کلید : یک XOR ساده از Round Key به حالت میانی. (key addition)
قبل از اولین راند، یک لایه key addition اعمال می شود. انگیزه برای این key addition اولیه در ادامه آمده است. هر لایه ، بعد از key addition قبلی در cipher (یا قبل از اولین در متن حمله known-plaintext ) می تواند به آسانی بدون دانستن کلید برداشته شود و بموجب آن در امنیت رمزنگاری شرکت نمی کند(همانند جایگردی اولیه و آخریه در DES ). key addition اولیه یا ترمینالی در چند طراحی از جمله IDEA ،SAFER و Blowfish بکار گرفته شده اند.
بمنظور برقراری تشابه بیشتر بین رمزنگار و معکوس آن از نظر ساختاری ، لایه ترکیب کننده در آخرین راند با لایه های ترکیب کننده در دیگر راند ها متفاوت است. می توان نشان داد که این عمل به هیچ طریق تاثیری در افزایش یا کاهش ایمنی رمزنگاری ندارد. این مشابه نبودن عملیات تعویض در آخرین راند DES است.
4. مشخصات
Rijndael یک رمزنگار بلوکی با تکرار، با طول بلوک متغیر و طول کلید متغیر است.طول کلید و طول بلوک می توانند بطور مستقل برابر 128 یا 192 یا 256 بیت باشد.
1.4 State و کلید رمز و تعداد راندها
عمل تبدیلات مختلف بر نتایج میانی ، حالت یا State نامیده می شود :
تعریف : نتیجه رمزنگاری میانی ، حالت نامیده می شود.
حالت می تواند بصورت یک آرایه مستطیلی از بایت ها تصویر شود.این آرایه 4 ردیف دارد. تعداد ستون ها با Nb نشان داده می شود و برابر است با طول بلوک تقسیم بر 32 .
کلید رمز بصورت مشابه بصورت یک آرایه مستطیلی از بایت ها تصویر می شود که دارای 4 ردیف است.
تعداد ستون های کلید رمز با Nk نشان داده می شود و برابر است با طول کلید تقسیم بر 32. این نمایش در شکل 1 نشان داده شده است.
در بعضی موارد ، این بلوک ها به صورت آرایه هایی از بردار های 4 بایتی 1 بعدی نیز در نظر گرفته می شوند، در حالی که هر بردار شامل ستون متناظر در نمایش آرایه مستطیلی است.این آرایه ها دارای طول هایی بترتیب برابر با 4 و 6و 8 و در رنج های 0..3 ، 0..5 یا 0..7 اندیس گذاری می شود. بعضی وقت ها آرایه های 4 بایتی به یک کلمه اشاره می شود. در جایی که لازم باشد 4 بایت منفرد در یک کلمه یا بردار 4 بایتی مشخص شود ، نشان گذاری (a,b,c,d) استفاده خواهد شد، بصورتی کهa ،b،c و d بایتهایی هستند که بترتیب در موقعیت های 0،1،2 و3 درون ستون ، بردار یا کلمه ای که در نظر گرفته شده اند ، قرار دارند.
شکل 1 مثالی از طرح بندی حالت(با Nb = 6 ) و کلید رمز (با Nk = 4 )
ورودی و خروجی که توسط Rijndael در واسط های خارجی آن استفاده می شود ، بصورت آرایه های تک بعدی از بایت های 8 بیتی با شماره گذاری صعودی از 0 تا 4*Nb-1 در نظر گرفته می شوند. این
بلوک ها دارای طول های 16 ، 24 و 32 بایتی هستند و آرایه ها در بازه های 0..15 ،0..23 ،یا 0..31 اندیس گذاری می شوند. کلید رمز بصورت آرایه های یک بعدی از بایت های 8 بیتی که بصورت صعودی از 0 تا 4*Nk-1 شماره گذاری شده اند،در نظر گرفته می شود.این بلوک ها دارای طول های 16 ، 24 و 32 بایتی هستند و آرایه ها در بازه های 0..15 ،0..23 ،یا 0..31 اندیس گذاری می شوند.
بایت های ورودی رمزنگار ، ( که اگر از مود کدگذاری ECB استفاده شود ، همان “plaintext” است) به بایت های State با ترتیب a0,0,a1,0,a2,0,a3,0,a0,1,a1,1,a2,1,a3,1,a4,1 … نگاشته می شود و بایت های cipher key (کلید رمز) به آرایه هایی با ترتیب k0,0,k1,0,k2,0,k3,0,k0,1,k1,1,k2,1,k3,1,k4,1 ... نگاشته می شوند. در پایان عملیات رمزنگاری ، خروجی رمزنگار از State با قرار دادن بایت های State در ترتیبی مشابه استخراج می شود.
بنابر این اگر n شاخص یک بعدی یک بایت درون یک بلاک باشد و شاخص دو بعدی (i ,j) باشد،داریم :
i = n mod 4 ; j = ën / 4û ; n = i + 4 * j
بعلاوه ، شاخص i همچنین شماره بایت درون یک کلمه یا بردار 4 بایتی است و j شاخص بردار یا کلمه (word) درون بلوک ضمیمه شده است.
تعداد راند ها بوسیله Nr نشان داده می شود و به مقادیر Nb و Nk بستگی دارد و در جدول 1 نشان داده شده است.
جدول 1 تعداد راند ها (Nr) بعنوان تابعی از طول کلید و بلوک
2.4 تبدیل راند
تبدیل راند ترکیبی از چهار تبدیل متفاوت است. در شبهه نشان گذاری c داریم :
Round(State,RoundKey)
{
ByteSub(State);
ShiftRow(State);
MixColumn(State);
AddRoundKey(State,RoundKey);
}
آخرین راند رمزنگار اندکی متفاوت است. و به این صورت تعریف می شود :
FinalRound(State,RoundKey)
{
ByteSub(State) ;
ShiftRow(State) ;
AddRoundKey(State,RoundKey);
}
در این نشان گذاری ، “functions” (Round, ByteSub, ShiftRow, …) بر روی آرایه هایی عمل می کنند که پوینتر (State, RoundKey) فراهم می کند.
می توان دیدکه راند نهایی ماننددیگر راندها هست با این تفاوت که در آن مرحله MixColumn حذف شده است.
اجزای تبدیلات در قسمت های بعدی معرفی می شوند.
1.2.4 تبدیل ByteSub
تبدیل Byte Sub یک جانشینی بایتی غیرخطی است ، که بر همه بایت های State بطور مستقل عمل می کند. جدول جانشینی(یا S-box ) معکوس پذیر است و با ترکیب دو تبدیل ساخته شده است :
1. ابتدا با نمایشی که در بخش 1.2 معرفی شد ، معکوس ضربی در GF(28) را میگیرد .’00’
را به خودش نگاشته می کند.
2. سپس تبدیل affine را که بصورت زیر تعریف می شود را اعمال می کند(روی GF(28) ) :
کاربرد S-box توصیف شده روی همه بایت های State بصورت زیر بیان می شود :
ByteSub(State)
شکل 2 نشان دهنده اثر تبدیل Byte Sub روی State است.
شکل 2 Byte Sub بر روی بایت های منفرد State عمل می کند.
معکوس ByteSub یک جانشینی بایتی است که در آن جدول معکوس اعمال می شود.این عمل بوسیله معکوس نگاشت affine بهمراه معکوس ضرب در (GF(28 انجام می شود.
2.2.4 تبدیل ShiftRow
در ShiftRow، ردیف های State بطور دوره ای روی آفست های مختلف شیفت داده می شود.ردیف 0 نباید شیفت داده شود، ردیف 1 روی c1 بایت شیفت داده می شود، ردیف 2 روی c2 بایت و ردیف 3 روی c3 بایت.
آفست های شیفت c1،c2 و c3 به طول بلوک Nb وابسته است. مقادیر مختلف در جدول 2 مشخص شده اند.
جدول 2 Shift offset ها برای طول بلوک های متفاوت.
عمل شیفت کردن ردیف های State روی آفست های مشخص بصورت زیر بیان می شود :
ShiftRow(State)
شکل 3 نشان دهنده اثر تبدیل ShiftRow روی State است.
شکل 3 عملShiftRow روی ردیف های State
عمل معکوس ShiftRow یک شیفت چرخشی از 3 ردیف پایین ، بترتیب روی بایت های Nb-C1 ، Nb-C2 ،Nb-C3 است.
در نتیجه بایتی که در موقعیت j ودر ردیف i است به موقعیت j+Nb-Ci) mod Nb) منتقل می شود.
3.2.4 تبدیل MixColumn
در Mixcolumn ، ستون های State بعنوان چندجمله ای هایی روی GF(28) در نظر گرفته می شوند و در یک چند جمله ای ثابت c(x) و به پیمانه x4 + 1 ضرب می شوند.c(x) بصورت زیر است :
c(x) = ‘03’x3 + ‘01’x2 + ‘01’x + ‘02’
این چتدجمله ای نسبت به x4 + 1 اول و درنتیجه معکوس پذیر است.همان طو ر که در بخش 2.2 گفته شد ، می توان این عمل را بصورت ضرب ماتریسی نوشت. اگر فرض کنیم b(x ) = c(x ) Ä a(x )
این عمل بر روی تمام ستون های State بصورت زیر بیان می شود :
MixColumn(State)
شکل 4 نشان دهنده اثر تبدیل MixColumn روی State است .
شکل 4 Mxcolumn بر روی ستون های State عمل می کند.
عمل معکوس MixColumn مشابه Mixcolumn است، هر ستون با ضرب در چندجمله ای ویژه d(x) که بصورت زیر تعریف می شود ، تبدیل می شود :
و به این صورت بیان می شود :
d(x)=’0B’x3 +’0D’x2 +’09’x +’0E’
4.2.4 Round Key addition
در این عمل ، یک Round Key بوسیله یک XOR بیتی ساده به State تعمال می شود . Round Key از طرف کلید رمز (Cipher Key) و بوسیله key schedule بدست می آید . طول Round Key به اندازه طول بلوک یعنی Nb است. تبدیلی که شامل XOR کردن یک Round Key بر State است بصورت زیر تعریف می شود :
AddRoundKey (State,RoundKey)
این تبدیل در شکل 5 نشان داده شده است.
شکل 5 Round Key در key addition بصورت XOR بیتی، روی State اعمال می شود.
AddRoundKey معکوس خودش هست.
3.4 Key schedule
. Round Key از طرف کلید رمز (Cipher Key) و بوسیله key schedule بدست می آید.و این شامل دو قسمت است : انتخاب Round Key و Key Expansion .اصل پایه ای از این قرار است :
· تعداد کل بیت های Round Key به اندازه طول بلوک ضرب در شماره راند بعلاوه یک است( بعنوان مثال برای طول بلوک 128 و راند 10 ، به 1408 بیت Round Key نیاز است)
· Cipher Key به یک Expanded Key بسط داده می شود.
· Round Key از این Expanded Key گرفته می شوند به این صورت که : Round Key اول شامل Nb کلمه اول است، دومین Round Key شامل Nb کلمه بعدیست و این روند ادامه میابد.
1.3.4 Key expansion
کلید بسط داده شده یک آرایه خطی 4 بایتی از کلمه ها است که با W[Nb*(Nr+1)] نشان داده می شود.Nk کلمه اول شامل Cipher Key است.تمام دیگر کلمات بصورت بازگشتی برحسب کلمات با اندیس های کوچکتر تعریف می شوند.تابع key expansion به مقدار Nk وابسته است.نسخه ای برای Nk های مساوی 6 یا کوجکتر از 6 وجود دارد و نسخه ای هم برای Nk بزرگتر از 6 وجود دارد.
برای Nk = 6 داریم :
KeyExpansion(byte Key[4*Nk] word W[Nb*(Nr+1)])
{
for(i = 0; i < Nk; i++)
W[i] = (Key[4*i],Key[4*i+1],Key[4*i+2],Key[4*i+3]);
for(i = Nk; i < Nb * (Nr + 1); i++)
{
temp = W[i - 1];
if (i % Nk == 0)
temp = SubByte(RotByte(temp)) ^ Rcon[i / Nk];
W[i] = W[i - Nk] ^ temp;
}
}
(SubByte(W در این تعریف ، تابعی است که یک کلمه 4 بیتی را باز می گرداند که هر بایت آن حاصل اعمال S-box Rijndael است که به موقعیت متناظر در ورودی اعمال شده است.
تابع (RotByte(W کلمه ای را بر میگرداند که بایت های یک جایگشت چرخه ای از ورودی است به نحوی که کلمات ورودی (a,b,c,d) کلمات خروجی(b,c,d,a) را تولید می کنند.
می توان دید که Nk کلمه اول با کلید رمز پر شده اند، هر کلمه w[i] برابر با حاصل عمل XOR بین کلمه قبلی ، [w[i-1 و کلمه با Nk موقعیت جلوتر ،[w[i-Nk است. برای کلماتی که درموقعیت هایی هستند که از مضارب Nk است، تبدیلی بر [w[i-1 اعمال می شود که قبل از XOR است و ثابت راند نیز XOR شده است. این تبدیل شامل یک شیفت چرخشی از بایت های درون کلمه (RotByte)،به همراه استفاده از جدولی است که به دنبال تمام بایت های کلمه میگردد (SubByte).
برای Nk > 6 داریم :
KeyExpansion(byte Key[4*Nk] word W[Nb*(Nr+1)])
{
for(i = 0; i < Nk; i++)
W[i] = (key[4*i],key[4*i+1],key[4*i+2],key[4*i+3]);
for(i = Nk; i < Nb * (Nr + 1); i++)
{
temp = W[i - 1];
if (i % Nk == 0)
temp = SubByte(RotByte(temp)) ^ Rcon[i / Nk];
else if (i % Nk == 4)
temp = SubByte(temp);
W[i] = W[i - Nk] ^ temp;
}
}
تفاوت با Nk =6 اینست که برای i-4 یک ضرب از Nk ، SubByteقبل از XOR به [w[i-1 اعمال شده است.
ثابت راند ، مستقل از Nk است و بصورت زیر تعریف می شود :
Rcon[i] = (RC[i],’00’,’00’,’00’)
و RC[i] نشان دهنده عنصری در GF(28) با مقدار xi-1 است و بموجب آن:
RC[1]=1 (‘01’ یعنی)
RC[i] = x (‘02’ یعنی) · (RC[i-1]) = x(i-1)
2.3.4 Round Key selection
کلید راند i بوسیله کلمات بافر کلید راند [w[Nb*i به[(w[Nb*(i+1 داده شده است. این عمل در شکل 6 نشان داده شده است.
شکل 6 key expansion و Round Key selection برای Nb=6 و Nk=4 .
توجه : key schedule را می توان بدون استفاده آشکار از آرایه [(w[Nb*(Nr+1 ایجاد کرد. برای زمان هایی که RAM کم است ، می توان Round Key را بصورت on-the-fly و با استفاده از بافر Nk کلمه و بدون محاسبات زیاد ، محاسبه کرد.
4.4 رمزنگار (Cipher)
رمزنگار Rijndael شامل موارد زیر است :
· یک Round Key addition اولیه؛
· تعداد Nr-1 راند؛
· و راند نهایی
در شبه کد زبان C به این صورت است :
Rijndael(State,CipherKey)
{
KeyExpansion(CipherKey,ExpandedKey) ;
AddRoundKey(State,ExpandedKey);
For( i=1 ; i
FinalRound(State,ExpandedKey + Nb*Nr); }
Key expansion را می توان پیشاپیش انجام داد و Rijndael را بر حسب آن مشخص کرد.
Rijndael(State,ExpandedKey)
{
AddRoundKey(State,ExpandedKey);
For( i=1 ; i
FinalRound(State,ExpandedKey + Nb*Nr);
}
توجه : Expanded Key (کلید بسط داده شده) باید همیشه از Cipher Key گرفته شود و نباید بطور مستقیم مشخص شود. هرچند محدودیتی برای انتخاب خود Cipher Key وجود ندارد..
5. inverse cipher
در معکوس یک راند ، ترتیب تبدیلهای درون راند معکوس می شود، و از این رو قسمت غیر خطی در آخر inverse round خواهد بود و ردیف ها پس از عمل معکوس MixColumn ،شیفت داده می شوند.
ساختار Rijndael بگونه ای است که ترتیب تبدیل ها با معکوسشان برابر است ، با این تفاوت که تبدیلات با معکوسشان جابجا می شوند و key schedule نیز تغییر می کند.
1.5 معکوس راندها
معکوس یک راند بصورت زیر است :
InvRound(State,RoundKey)
{
AddRoundKey(State,RoundKey);
InvMixColumn(State);
InvShiftRow(State);
InvByteSub(State);
}
و معکوس راند آخر بصورت زیر است :
InvFinalRound(State,RoundKey)
{
AddRoundKey(State,RoundKey);
InvShiftRow(State);
InvByteSub(State);
}
معکوس یک متغیر دو دوری رایندل(inverse of a two-round variant of Rijndael) شامل معکوس راند آخر بهمراه معکوس یک راند معمولی و بهمراه Round Key Addition است. داریم :
AddRoundKey(State,ExpandedKey+2*Nb);
InvShiftRow(State);
InvByteSub(State);
AddRoundKey(State,ExpandedKey+Nb);
InvMixColumn(State);
InvShiftRow(State);
InvByteSub(State);
AddRoundKey(State,ExpandedKey);
2.5 ساختار inverse cipher متناظر
معکوس یک متغیر دو دوری رایندل می تواند بصورت زیر نیز بیان شود :
AddRoundKey(State,ExpandedKey+2*Nb);
InvByteSub(State);
InvShiftRow(State);
InvMixColumn(State);
AddRoundKey(State,I_ExpandedKey+Nb);
InvByteSub(State);
InvShiftRow(State);
AddRoundKey(State,ExpandedKey);
معکوس راندها و معکوس راند آخر بصورت زیر بیان می شود :
I_Round(State,I_RoundKey)
{
InvByteSub(State);
InvShiftRow(State);
InvMixColumn(State);
AddRoundKey(State,I_RoundKey);
}
I_FinalRound(State,I_RoundKey)
{
InvByteSub(State);
InvShiftRow(State);
AddRoundKey(State,RoundKey0);
معکوس رمزنگار رایندل نیز بصورت زیر بیان می شود :
I_Rijndael(State,CipherKey)
{
I_KeyExpansion(CipherKey,I_ExpandedKey) ;
AddRoundKey(State,I_ExpandedKey+ Nb*Nr);
For( i=Nr-1 ; i>0 ; i-- ) Round(State,I_ExpandedKey+ Nb*i) ;
FinalRound(State,I_ExpandedKey);
}
بسط دادن کلید برای معکوس رمزنگار ، بصورت زیر تعریف می شود :
1. اعمال Key Expansion.
2. اعمال InvMixColumn به همه Round Key ها بجز اولین و آخرینشان.
بصورت شبه کد زبان C بصورت زیر خواهد بود :
I_KeyExpansion(CipherKey,I_ExpandedKey)
{
KeyExpansion(CipherKey,I_ExpandedKey);
for( i=1 ; i < Nr ; i++ )
InvMixColumn(I_ExpandedKey + Nb*i) ;
}