LSH (دالة التجزئة)

LSH هي دالة تجزئة تشفيرية صُممت عام 2014 في كوريا الجنوبية لتوفير سلامة البيانات في بيئات البرمجيات العامة مثل أجهزة الكمبيوتر الشخصية والأجهزة الذكية . ^{[ 1 ]} تُعد LSH إحدى خوارزميات التشفير المعتمدة من قِبل البرنامج الكوري للتحقق من صحة وحدات التشفير (KCMVP)، وهي المعيار الوطني لكوريا الجنوبية (KS X 3262).

مواصفة

يظهر الشكل التالي البنية العامة لدالة التجزئة LSH.

تعتمد دالة التجزئة LSH على بنية Merkle-Damgård ذات الأنابيب العريضة مع إضافة أصفار. تتكون عملية تجزئة الرسائل في LSH من المراحل الثلاث التالية.

التهيئة :
- إضافة أصفار إلى رسالة سلسلة بتات معينة.
- تحويل رسالة سلسلة البتات المبطنة إلى كتل رسائل مصفوفة من 32 كلمة.
- تهيئة متغير التسلسل باستخدام متجه التهيئة.
الضغط :
- تحديث متغيرات التسلسل عن طريق تكرار دالة الضغط باستخدام كتل الرسائل.
الحسم :
- جيل من $n$ قيمة التجزئة ذات البتات من متغير السلسلة النهائي.

دالة التجزئة LSH المدخلات: رسالة سلسلة بت $m$ الناتج: قيمة التجزئة $h\in \{0,1\}^{n}$ إجراء $\qquad$ حشو الأصفار الواحدية $m$ $\qquad$ جيل $t$ كتل الرسائل $\{{\textsf {M}}^{(i)}\}_{i=0}^{t-1}$ ، أين $t={\Big \lceil }{\frac {\|m\|+1}{32w}}{\Big \rceil }$ من سلسلة البتات المبطنة $\qquad$ ${\textsf {CV}}^{(0)}\leftarrow {\textsf {IV}}$ $\qquad$ ل $i=0$ ل $(t-1)$ يفعل $\qquad$ $\qquad$ ${\textsf {CV}}^{(i+1)}\leftarrow {\textrm {CF}}({\textsf {CV}}^{(i)},{\textsf {M}}^{(i)})$ $\qquad$ نهاية لـ $\qquad$ $h\leftarrow {\textrm {FIN}}_{n}({\textsf {CV}}^{(t)})$ $\qquad$ يعود $h$

مواصفات دالة التجزئة LSH هي كما يلي.

مواصفات دالة التجزئة LSH
الخوارزمية	حجم التجزئة بالبتات ( $n$ )	عدد الدوال المتدرجة ( $N_{s}$ )	ربط أحجام متغيرة بالبتات	حجم كتلة الرسالة بالبتات	حجم الكلمة بالبتات ( $w$ )
LSH-256-224	224	26	512	1024	32
LSH-256-256	256	26	512	1024	32
LSH-512-224	224	28	1024	2048	64
LSH-512-256	256
LSH-512-384	384
LSH-512-512	512

التهيئة

يترك $m$ لنفترض أن لدينا سلسلة بتات معينة من الرسائل. $m$ يتم إضافة أصفار تساوي واحدًا إلى نهاية السلسلة، أي يتم إلحاق البت '1' بنهاية السلسلة. $m$ وتُضاف الأصفار إلى البتات حتى يصبح طول البتات للرسالة المُضافة هو $32wt$ ، أين $t=\lceil (|m|+1)/32w\rceil$ و $\lceil x\rceil$ هو أصغر عدد صحيح لا يقل عن $x$ .

يترك $m_{p}=m_{0}\|m_{1}\|\ldots \|m_{(32wt-1)}$ كن مملوءًا بالأصفار والآحاد $32wt$ سلسلة بتات $m$ . ثم $m_{p}$ يُعتبر $4wt$ مصفوفة بايت $m_{a}=(m[0],\ldots ,m[4wt-1])$ ، أين $m[k]=m_{8k}\|m_{(8k+1)}\|\ldots \|m_{(8k+7)}$ للجميع $0\leq k\leq (4wt-1)$ . ال $4wt$ مصفوفة بايت $m_{a}$ يتحول إلى $32t$ مصفوفة الكلمات ${\textsf {M}}=(M[0],\ldots ,M[32t-1])$ على النحو التالي.

$M[s]\leftarrow m[ws/8+(w/8-1)]\|\ldots \|m[ws/8+1]\|m[ws/8]$ $(0\leq s\leq (32t-1))$

من مصفوفة الكلمات ${\textsf {M}}$ ، نُعرّف $t$ كتل رسائل مصفوفة من 32 كلمة $\{{\textsf {M}}^{(i)}\}_{i=0}^{t-1}$ على النحو التالي.

${\textsf {M}}^{(i)}\leftarrow (M[32i],M[32i+1],\ldots ,M[32i+31])$ $(0\leq i\leq (t-1))$

متغير ربط المصفوفة المكونة من 16 كلمة ${\textsf {CV}}^{(0)}$ يتم تهيئتها إلى متجه التهيئة ${\textsf {IV}}$ .

${\textsf {CV}}^{(0)}[l]\leftarrow {\textsf {IV}}[l]$ $(0\leq l\leq 15)$

متجه التهيئة ${\textsf {IV}}$ كما يلي. في الجداول التالية، يتم التعبير عن جميع القيم بصيغة النظام الست عشري.

متجه التهيئة LSH-256-224
${\textsf {IV}}[0]$	${\textsf {IV}}[1]$	${\textsf {IV}}[2]$	${\textsf {IV}}[3]$	${\textsf {IV}}[4]$	${\textsf {IV}}[5]$	${\textsf {IV}}[6]$	${\textsf {IV}}[7]$
068608D3	62D8F7A7	D76652AB	4C600A43	BDC40AA8	1ECA0B68	DA1A89BE	3147D354
${\textsf {IV}}[8]$	${\textsf {IV}}[9]$	${\textsf {IV}}[10]$	${\textsf {IV}}[11]$	${\textsf {IV}}[12]$	${\textsf {IV}}[13]$	${\textsf {IV}}[14]$	${\textsf {IV}}[15]$
707EB4F9	F65B3862	6B0B2ABE	56B8EC0A	CF237286	EE0D1727	33636595	8BB8D05F

متجه تهيئة LSH-256-256
${\textsf {IV}}[0]$	${\textsf {IV}}[1]$	${\textsf {IV}}[2]$	${\textsf {IV}}[3]$	${\textsf {IV}}[4]$	${\textsf {IV}}[5]$	${\textsf {IV}}[6]$	${\textsf {IV}}[7]$
46A10F1F	FDDCE486	B41443A8	198E6B9D	3304388D	B0F5A3C7	B36061C4	7ADBD553
${\textsf {IV}}[8]$	${\textsf {IV}}[9]$	${\textsf {IV}}[10]$	${\textsf {IV}}[11]$	${\textsf {IV}}[12]$	${\textsf {IV}}[13]$	${\textsf {IV}}[14]$	${\textsf {IV}}[15]$
105D5378	2F74DE54	5C2F2D95	F2553FBE	8051357A	138668C8	47AA4484	E01AFB41

متجه التهيئة LSH-512-224
${\textsf {IV}}[0]$	${\textsf {IV}}[1]$	${\textsf {IV}}[2]$	${\textsf {IV}}[3]$
0C401E9FE8813A55	4A5F446268FD3D35	FF13E452334F612A	F8227661037E354A
${\textsf {IV}}[4]$	${\textsf {IV}}[5]$	${\textsf {IV}}[6]$	${\textsf {IV}}[7]$
A5F223723C9CA29D	95D965A11AED3979	01E23835B9AB02CC	52D49CBAD5B30616
${\textsf {IV}}[8]$	${\textsf {IV}}[9]$	${\textsf {IV}}[10]$	${\textsf {IV}}[11]$
9E5C2027773F4ED3	66A5C8801925B701	22BBC85B4C6779D9	C13171A42C559C23
${\textsf {IV}}[12]$	${\textsf {IV}}[13]$	${\textsf {IV}}[14]$	${\textsf {IV}}[15]$
31E2B67D25BE3813	D522C4DEED8E4D83	A79F5509B43FBAFE	E00D2CD88B4B6C6A

متجه التهيئة LSH-512-256
${\textsf {IV}}[0]$	${\textsf {IV}}[1]$	${\textsf {IV}}[2]$	${\textsf {IV}}[3]$
6DC57C33DF989423	D8EA7F6E8342C199	76DF8356F8603AC4	40F1B44DE838223A
${\textsf {IV}}[4]$	${\textsf {IV}}[5]$	${\textsf {IV}}[6]$	${\textsf {IV}}[7]$
39FFE7CFC31484CD	39C4326CC5281548	8A2FF85A346045D8	FF202AA46DBDD61E
${\textsf {IV}}[8]$	${\textsf {IV}}[9]$	${\textsf {IV}}[10]$	${\textsf {IV}}[11]$
CF785B3CD5FCDB8B	1F0323B64A8150BF	FF75D972F29EA355	2E567F30BF1CA9E1
${\textsf {IV}}[12]$	${\textsf {IV}}[13]$	${\textsf {IV}}[14]$	${\textsf {IV}}[15]$
B596875BF8FF6DBA	FCCA39B089EF4615	ECFF4017D020B4B6	7E77384C772ED802

متجه التهيئة LSH-512-384
${\textsf {IV}}[0]$	${\textsf {IV}}[1]$	${\textsf {IV}}[2]$	${\textsf {IV}}[3]$
53156A66292808F6	B2C4F362B204C2BC	B84B7213BFA05C4E	976CEB7C1B299F73
${\textsf {IV}}[4]$	${\textsf {IV}}[5]$	${\textsf {IV}}[6]$	${\textsf {IV}}[7]$
DF0CC63C0570AE97	DA4441BAA486CE3F	6559F5D9B5F2ACC2	22DACF19B4B52A16
${\textsf {IV}}[8]$	${\textsf {IV}}[9]$	${\textsf {IV}}[10]$	${\textsf {IV}}[11]$
BBCDACEFDE80953A	C9891A2879725B3E	7C9FE6330237E440	A30BA550553F7431
${\textsf {IV}}[12]$	${\textsf {IV}}[13]$	${\textsf {IV}}[14]$	${\textsf {IV}}[15]$
BB08043FB34E3E30	A0DEC48D54618EAD	150317267464BC57	32D1501FDE63DC93

متجه تهيئة LSH-512-512
${\textsf {IV}}[0]$	${\textsf {IV}}[1]$	${\textsf {IV}}[2]$	${\textsf {IV}}[3]$
ADD50F3C7F07094E	E3F3CEE8F9418A4F	B527ECDE5B3D0AE9	2EF6DEC68076F501
${\textsf {IV}}[4]$	${\textsf {IV}}[5]$	${\textsf {IV}}[6]$	${\textsf {IV}}[7]$
8CB994CAE5ACA216	FBB9EAE4BBA48CC7	650A526174725FEA	1F9A61A73F8D8085
${\textsf {IV}}[8]$	${\textsf {IV}}[9]$	${\textsf {IV}}[10]$	${\textsf {IV}}[11]$
B6607378173B539B	1BC99853B0C0B9ED	DF727FC19B182D47	DBEF360CF893A457
${\textsf {IV}}[12]$	${\textsf {IV}}[13]$	${\textsf {IV}}[14]$	${\textsf {IV}}[15]$
4981F5E570147E80	D00C4490CA7D3E30	5D73940C0E4AE1EC	894085E2EDB2D819

ضغط

في هذه المرحلة، $t$ كتل رسائل مصفوفة من 32 كلمة $\{{\textsf {M}}^{(i)}\}_{i=0}^{t-1}$ والتي يتم إنشاؤها من رسالة $m$ في مرحلة التهيئة، يتم ضغط البيانات من خلال تكرار دوال الضغط. دالة الضغط ${\textrm {CF}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{32}\rightarrow {\mathcal {W}}^{16}$ له مدخلان؛ $i$ متغير ربط مكون من 16 كلمة ${\textsf {CV}}^{(i)}$ و $i$ كتلة رسالة مكونة من 32 كلمة ${\textsf {M}}^{(i)}$ ويعيد ذلك $(i+1)$ متغير ربط مكون من 16 كلمة ${\textsf {CV}}^{(i+1)}$ هنا وفيما بعد، ${\mathcal {W}}^{t}$ يرمز إلى مجموعة جميع $t$ مصفوفات الكلمات لـ $t\geq 1$ .

تُستخدم الوظائف الأربع التالية في وظيفة الضغط:

وظيفة توسيع الرسائل ${\textrm {MsgExp}}:{\mathcal {W}}^{32}\rightarrow {\mathcal {W}}^{16(Ns+1)}$
وظيفة إضافة الرسائل ${\textrm {MsgAdd}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}$
وظيفة المزج ${\textrm {Mix}}_{j}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}$
دالة تبديل الكلمات ${\textrm {WordPerm}}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}$

يوضح الشكل التالي البنية العامة لوظيفة الضغط.

في دالة الضغط، دالة توسيع الرسالة ${\textrm {MsgExp}}$ يُنشئ $(N_{s}+1)$ رسائل فرعية مكونة من 16 كلمة $\{{\textsf {M}}_{j}^{(i)}\}_{j=0}^{N_{s}}$ من المعطى ${\textsf {M}}^{(i)}$ . يترك ${\textsf {T}}=(T[0],\ldots ,T[15])$ أن تكون مصفوفة مؤقتة مكونة من 16 كلمة مضبوطة على $i$ متغير السلسلة رقم -th ${\textsf {CV}}^{(i)}$ . ال $j$ دالة الخطوة رقم - ${\textrm {Step}}_{j}$ يحتوي على مدخلين ${\textsf {T}}$ و ${\textsf {M}}_{j}^{(i)}$ التحديثات ${\textsf {T}}$ ، أي، ${\textsf {T}}\leftarrow {\textrm {Step}}_{j}\left({\textsf {T}},{\textsf {M}}_{j}^{(i)}\right)$ يتم تنفيذ جميع وظائف الخطوات بالترتيب $j=0,\ldots ,N_{s}-1$ ثم واحد آخر ${\textrm {MsgAdd}}$ عملية بواسطة ${\textsf {M}}_{N_{s}}^{(i)}$ ثم يتم المضي قدماً، و $(i+1)$ متغير السلسلة رقم -th ${\textsf {CV}}^{(i+1)}$ تم ضبطه على ${\textsf {T}}$ فيما يلي شرح مفصل لعملية وظيفة الضغط.

دالة الضغط ${\textrm {CF}}$ المدخلات: الـ $i$ متغير السلسلة رقم -th ${\textsf {CV}}^{(i)}\in {\mathcal {W}}^{16}$ و $i$ كتلة الرسائل رقم -th ${\textsf {M}}^{(i)}\in {\mathcal {W}}^{32}$ الناتج: الـ $(i+1)$ متغير السلسلة رقم -th ${\textsf {CV}}^{(i+1)}\in {\mathcal {W}}^{16}$ إجراء $\qquad$ $\{{\textsf {M}}_{j}^{(i)}\}_{j=0}^{N_{s}}\leftarrow {\textrm {MsgExp}}\left({\textsf {M}}^{(i)}\right)$ $\qquad$ ${\textsf {T}}\leftarrow {\textsf {CV}}^{(i)}$ $\qquad$ ل $j=0$ ل $(N_{s}-1)$ يفعل $\qquad$ $\qquad$ ${\textsf {T}}\leftarrow {\textrm {Step}}_{j}\left({\textsf {T}},{\textsf {M}}_{j}^{(i)}\right)$ $\qquad$ نهاية لـ $\qquad$ ${\textsf {CV}}^{(i+1)}\leftarrow {\textrm {MsgAdd}}\left({\textsf {T}},{\textsf {M}}_{N_{s}}^{(i)}\right)$ $\qquad$ يعود ${\textsf {CV}}^{(i+1)}$

هنا $j$ دالة الخطوة رقم - ${\textrm {Step}}_{j}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}$ وهو كما يلي.

${\textrm {Step}}_{j}:={\textrm {WordPerm}}\circ {\textrm {Mix}}_{j}\circ {\textrm {MsgAdd}}$ $(0\leq j\leq (N_{s}-1))$

يوضح الشكل التالي $j$ دالة الخطوة رقم - ${\textrm {Step}}_{j}$ من وظيفة الضغط.

{\displaystyle j} — ال $j$ دالة الخطوة رقم - ${\textrm {Step}}_{j}$

وظيفة توسيع الرسائل MsgExp

يترك ${\textsf {M}}^{(i)}=(M^{(i)}[0],\ldots ,M^{(i)}[31])$ كن $i$ كتلة رسالة مصفوفة من 32 كلمة. دالة توسيع الرسالة ${\textrm {MsgExp}}$ يُنشئ $(N_{s}+1)$ رسائل فرعية مكونة من 16 كلمة $\{{\textsf {M}}_{j}^{(i)}\}_{j=0}^{N_{s}}$ من كتلة الرسائل ${\textsf {M}}^{(i)}$ الرسالتان الفرعيتان الأوليان ${\textsf {M}}_{0}^{(i)}=(M_{0}^{(i)}[0],\ldots ,M_{0}^{(i)}[15])$ و ${\textsf {M}}_{1}^{(i)}=(M_{1}^{(i)}[0],\ldots ,M_{1}^{(i)}[15])$ يتم تعريفها على النحو التالي.

${\textsf {M}}_{0}^{(i)}\leftarrow (M^{(i)}[0],M^{(i)}[1],\ldots ,M^{(i)}[15])$
${\textsf {M}}_{1}^{(i)}\leftarrow (M^{(i)}[16],M^{(i)}[17],\ldots ,M^{(i)}[31])$

الرسائل الفرعية التالية $\{{\textsf {M}}_{j}^{(i)}=(M_{j}^{(i)}[0],\ldots ,M_{j}^{(i)}[15])\}_{j=2}^{N_{s}}$ يتم توليدها على النحو التالي.

${\textsf {M}}_{j}^{(i)}[l]\leftarrow {\textsf {M}}_{j-1}^{(i)}[l]\boxplus {\textsf {M}}_{j-2}^{(i)}[\tau (l)]$ $(0\leq l\leq 15,\ 2\leq j\leq N_{s})$

هنا $\tau$ هل التبديل على $\mathbb {Z} _{16}$ تم تعريفها على النحو التالي.

التبديل ${\displaystyle \tau$
$l$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$\tau (l)$	3	2	0	1	7	4	5	6	11	10	8	9	15	12	13	14

وظيفة إضافة الرسائل MsgAdd

لمصفوفتين من 16 كلمة ${\textsf {X}}=(X[0],\ldots ,X[15])$ و ${\textsf {Y}}=(Y[0],\ldots ,Y[15])$ وظيفة إضافة الرسائل ${\textrm {MsgAdd}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}$ يُعرَّف على النحو التالي.

${\textrm {MsgAdd}}({\textsf {X}},{\textsf {Y}}):=(X[0]\oplus Y[0],\ldots ,X[15]\oplus Y[15])$

وظيفة المزج

ال $j$ وظيفة المزج رقم -th ${\textrm {Mix}}_{j}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}$ يقوم بتحديث مصفوفة الكلمات الـ 16 ${\textsf {T}}=(T[0],\ldots ,T[15])$ عن طريق خلط كل زوج من الكلمات؛ $T[l]$ و $T[l+8]$ ل $(0\leq l<8)$ . ل $0\leq j<N_{s}$ ، وظيفة المزج ${\textrm {Mix}}_{j}$ تتم العملية على النحو التالي.

$(T[l],T[l+8])\leftarrow {\textrm {Mix}}_{j,l}(T[l],T[l+8])$ $(0\leq l<8)$

هنا ${\textrm {Mix}}_{j,l}$ هي دالة مزج كلمتين. ليكن $X$ و $Y$ كن كلمات. دالة المزج بين كلمتين ${\textrm {Mix}}_{j,l}:{\mathcal {W}}^{2}\rightarrow {\mathcal {W}}^{2}$ يُعرَّف على النحو التالي.

دالة مزج كلمتين ${\textrm {Mix}}_{j,l}$ المدخلات: كلمات $X$ و $Y$ الناتج: كلمات $X$ و $Y$ إجراء $\qquad$ $X\leftarrow X\boxplus Y$ ; $\qquad X\leftarrow X^{\lll \alpha _{j}}$ ; $\qquad$ $X\leftarrow X\oplus SC_{j}[l]$ ; $\qquad$ $Y\leftarrow X\boxplus Y$ ; $\qquad Y\leftarrow Y^{\lll \beta _{j}}$ ; $\qquad$ $X\leftarrow X\boxplus Y$ ; $\qquad Y\leftarrow Y^{\lll \gamma _{l}}$ ; $\qquad$ يعود $X$ ، $Y$ ;

وظيفة المزج بين كلمتين ${\textrm {Mix}}_{j,l}$ يظهر ذلك في الشكل التالي.

{\displaystyle {\textrm {ميكس}}_{j,l}(X,Y)} — وظيفة المزج بين كلمتين ${\textrm {Mix}}_{j,l}(X,Y)$

كميات دوران البت $\alpha _{j}$ ، $\beta _{j}$ ، $\gamma _{l}$ يستخدم في ${\textrm {Mix}}_{j,l}$ يتم عرضها في الجدول التالي.

كميات دوران البت $\alpha _{j}$ ، $\beta _{j}$ ، و $\gamma _{l}$
$w$	$j$	$\alpha _{j}$	$\beta _{j}$	$\gamma _{1}$	$\gamma _{2}$	$\gamma _{3}$	$\gamma _{4}$	$\gamma _{5}$	$\gamma _{6}$	$\gamma _{7}$
32	حتى	29	1	8	16	24	24	16	8	0
32	غريب	5	17	8	16	24	24	16	8	0
64	حتى	23	59	16	32	48	8	24	40	56
64	غريب	7	3	16	32	48	8	24	40	56

ال $j$ ثابت مصفوفة من 8 كلمات ${\textsf {SC}}_{j}=(SC_{j}[0],\ldots ,SC_{j}[7])$ يستخدم في ${\textrm {Mix}}_{j,l}$ ل $0\leq l<8$ يتم تعريفها على النحو التالي. ثابت المصفوفة الأولي المكون من 8 كلمات ${\textsf {SC}}_{0}=(SC_{0}[0],\ldots ,SC_{0}[7])$ يتم تعريفها في الجدول التالي. لـ $1\leq j<N_{s}$ ، ال $j$ الثابت رقم - ${\textsf {SC}}_{j}=(SC_{j}[0],\ldots ,SC_{j}[7])$ يتم إنشاؤه بواسطة $SC_{j}[l]\leftarrow SC_{j-1}[l]\boxplus SC_{j-1}[l]^{\lll 8}$ ل $0\leq l<8$ .

ثابت المصفوفة الأولي المكون من 8 كلمات ${\textsf {SC}}_{0}$
	$w=32$	$w=64$
$SC_{0}[0]$	917caf90	97884283c938982a
$SC_{0}[1]$	6c1b10a2	ba1fca93533e2355
$SC_{0}[2]$	6f352943	c519a2e87aeb1c03
$SC_{0}[3]$	cf778243	9a0fc95462af17b1
$SC_{0}[4]$	2ceb7472	fc3dda8ab019a82b
$SC_{0}[5]$	29e96ff2	02825d079a895407
$SC_{0}[6]$	8a9ba428	79f2d0a7ee06a6f7
$SC_{0}[7]$	2eeb2642	d76d15eed9fdf5fe

دالة تبديل الكلمات WordPerm

يترك ${\textsf {X}}=(X[0],\ldots ,X[15])$ ليكن مصفوفة من 16 كلمة. دالة تبديل الكلمات ${\textrm {WordPerm}}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}$ يُعرَّف على النحو التالي.

${\textrm {WordPerm}}({\textsf {X}})=(X[\sigma (0)],\ldots ,X[\sigma (15)])$

هنا $\sigma$ هل التبديل على $\mathbb {Z} _{16}$ كما هو موضح في الجدول التالي.

التبديل ${\displaystyle \sigma$
$l$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$\sigma (l)$	6	4	5	7	12	15	14	13	2	0	1	3	8	11	10	9

إتمام الإجراءات

دالة الإنهاء ${\textrm {FIN}}_{n}:{\mathcal {W}}^{16}\rightarrow \{0,1\}^{n}$ عمليات الإرجاع $n$ قيمة التجزئة ذات البت $h$ من متغير التسلسل النهائي ${\textsf {CV}}^{(t)}=(CV^{(t)}[0],\ldots ,CV^{(t)}[15])$ . متى ${\textsf {H}}=(H[0],\ldots ,H[7])$ هو متغير مكون من 8 كلمات و ${\textsf {h}}_{\textsf {b}}=(h_{b}[0],\ldots ,h_{b}[w-1])$ هو $w$ متغير بايت، دالة الإنهاء ${\textrm {FIN}}_{n}$ يقوم بالإجراء التالي.

$H[l]\leftarrow CV^{(t)}[l]\oplus CV^{(t)}[l+8]$ $(0\leq l\leq 7)$
$h_{b}[s]\leftarrow H[\lfloor 8s/w\rfloor ]_{[7:0]}^{\ggg (8s\mod w)}$ $(0\leq s\leq (w-1))$
$h\leftarrow (h_{b}[0]\|\ldots \|h_{b}[w-1])_{[0:n-1]}$

هنا، $X_{[i:j]}$ يشير $x_{i}\|x_{i-1}\|\ldots \|x_{j}$ ، سلسلة البتات الفرعية للكلمة $X$ ل $i\geq j$ . و $x_{[i:j]}$ يشير $x_{i}\|x_{i+1}\|\ldots \|x_{j}$ ، سلسلة البتات الفرعية لـ $l$ سلسلة بت $x=x_{0}\|x_{1}\|\ldots \|x_{l-1}$ ل $i\leq j$ .

حماية

يُعدّ LSH آمنًا ضد الهجمات المعروفة على دوال التجزئة حتى الآن. كما أنه مقاوم للتصادم. $q<2^{n/2}$ ومقاومة للصورة السابقة ومقاومة للصورة السابقة الثانية لـ $q<2^{n}$ في نموذج التشفير المثالي، حيث $q$ يمثل هذا عددًا من الاستعلامات لبنية LSH. ^{[ 1 ]} تُعتبر LSH-256 آمنة ضد جميع هجمات دالة التجزئة الحالية عندما يكون عدد الخطوات 13 أو أكثر، بينما تُعتبر LSH-512 آمنة إذا كان عدد الخطوات 14 أو أكثر. تجدر الإشارة إلى أن الخطوات التي تعمل كهامش أمان تُمثل 50% من دالة الضغط. ^{[ 1 ]}

أداء

يتفوق LSH على SHA-2/3 في العديد من منصات البرامج. يوضح الجدول التالي سرعة تجزئة الرسائل بحجم 1 ميجابايت باستخدام LSH على عدة منصات.

سرعة تجزئة الرسائل بحجم 1 ميجابايت لـ LSH (دورات/بايت) ^{[ 1 ]}
منصة	P1 ^{[ أ ]}	P2 ^{[ ب ]}	P3 ^{[ ج ]}	P4 ^{[ د ]}	P5 ^{[ e ]}	P6 ^{[ f ]}	P7 ^{[ g ]}	P8 ^{[ h ]}
LSH-256- $n$	3.60	3.86	5.26	3.89	11.17	15.03	15.28	14.84
LSH-512- $n$	2.39	5.04	7.76	5.52	8.94	18.76	19.00	18.10

↑ معالج Intel Core i7-4770K بسرعة 3.5 جيجاهرتز (Haswell)، نظام Ubuntu 12.04 64 بت، برنامج GCC 4.8.1 مع الخيار "-m64 -mavx2 -O3"
↑ معالج Intel Core i7-2600K بسرعة 3.40 جيجاهرتز (Sandy Bridge)، نظام Ubuntu 12.04 64 بت، برنامج GCC 4.8.1 مع الخيار "-m64 -msse4 -O3"
↑ معالج Intel Core 2 Quad Q9550 بسرعة 2.83 جيجاهرتز (يوركفيلد)، نظام التشغيل Windows 7 32 بت، برنامج Visual Studio 2012
↑ AMD FX-8350 @ 4GHz (Piledriver)، Ubuntu 12.04 64-bit، GCC 4.8.1 مع "-m64 -mxop -O3"
↑ معالج سامسونج Exynos 5250 ARM Cortex-A15 ثنائي النواة بسرعة 1.7 جيجاهرتز (Huins ACHRO 5250)، نظام أندرويد 4.1.1
↑ معالج كوالكوم سنابدراجون 800 كرايت 400 رباعي النواة بسرعة 2.26 جيجاهرتز (إل جي جي 2)، نظام أندرويد 4.4.2
↑ معالج كوالكوم سنابدراجون 800 كرايت 400 رباعي النواة بسرعة 2.3 جيجاهرتز (سامسونج جالاكسي إس 4)، نظام أندرويد 4.2.2
↑ معالج كوالكوم سنابدراجون 400 كرايت 300 ثنائي النواة بسرعة 1.7 جيجاهرتز (سامسونج جالاكسي إس 4 ميني)، نظام أندرويد 4.2.2

الجدول التالي هو مقارنة على المنصة القائمة على Haswell، تم قياس LSH على منصة Intel Core i7-4770k @ 3.5 GHz رباعية النواة، وتم قياس الآخرين على منصة Intel Core i5-4570S @ 2.9 GHz رباعية النواة.

قياس سرعة LSH و SHA-2 والمتأهلين النهائيين لـ SHA-3 على المنصة القائمة على وحدة المعالجة المركزية Haswell (دورات/بايت) ^{[ 1 ]}
الخوارزمية	حجم الرسالة بالبايت
الخوارزمية	طويل	4096	1536	576	64	8
LSH-256-256	3.60	3.71	3.90	4.08	8.19	65.37
Skein-512-256	5.01	5.58	5.86	6.49	13.12	104.50
بليك-256	6.61	7.63	7.87	9.05	16.58	72.50
غروستل-256	9.48	10.68	12.18	13.71	37.94	227.50
كيكاك-256	10.56	10.52	9.90	11.99	23.38	187.50
SHA-256	10.82	11.91	12.26	13.51	24.88	106.62
JH-256	14.70	15.50	15.94	17.06	31.94	257.00
LSH-512-512	2.39	2.54	2.79	3.31	10.81	85.62
Skein-512-512	4.67	5.51	5.80	6.44	13.59	108.25
بليك-512	4.96	6.17	6.82	7.38	14.81	116.50
SHA-512	7.65	8.24	8.69	9.03	17.22	138.25
غروستل-512	12.78	15.44	17.30	17.99	51.72	417.38
JH-512	14.25	15.66	16.14	17.34	32.69	261.00
كيكاك-512	16.36	17.86	18.46	20.35	21.56	171.88

الجدول التالي تم قياسه على منصة Samsung Exynos 5250 ARM Cortex-A15 @ 1.7 GHz ثنائية النواة.

قياس سرعة LSH و SHA-2 و SHA-3 النهائية على المنصة القائمة على وحدة المعالجة المركزية Exynos 5250 ARM Cortex-A15 (دورات/بايت) ^{[ 1 ]}
الخوارزمية	حجم الرسالة بالبايت
الخوارزمية	طويل	4096	1536	576	64	8
LSH-256-256	11.17	11.53	12.16	12.63	22.42	192.68
Skein-512-256	15.64	16.72	18.33	22.68	75.75	609.25
بليك-256	17.94	19.11	20.88	25.44	83.94	542.38
SHA-256	19.91	21.14	23.03	28.13	90.89	578.50
JH-256	34.66	36.06	38.10	43.51	113.92	924.12
كيكاك-256	36.03	38.01	40.54	48.13	125.00	1000.62
غروستل-256	40.70	42.76	46.03	54.94	167.52	1020.62
LSH-512-512	8.94	9.56	10.55	12.28	38.82	307.98
بليك-512	13.46	14.82	16.88	20.98	77.53	623.62
Skein-512-512	15.61	16.73	18.35	22.56	75.59	612.88
JH-512	34.88	36.26	38.36	44.01	116.41	939.38
SHA-512	44.13	46.41	49.97	54.55	135.59	1088.38
كيكاك-512	63.31	64.59	67.85	77.21	121.28	968.00
غروستل-512	131.35	138.49	150.15	166.54	446.53	3518.00

متجهات الاختبار

فيما يلي متجهات الاختبار لتقنية LSH لكل طول هضم. جميع القيم معبر عنها بالصيغة الست عشرية.

LSH-256-224("abc") = F7 C5 3B A4 03 4E 70 8E 74 FB A4 2E 55 99 7C A5 12 6B B7 62 36 88 F8 53 42 F7 37 32

LSH-256-256("abc") = 5F BF 36 5D AE A5 44 6A 70 53 C5 2B 57 40 4D 77 A0 7A 5F 48 A1 F7 C1 96 3A 08 98 با 1B 71 47 41

LSH-512-224("abc") = D1 68 32 34 51 3E C5 69 83 94 57 1E AD 12 8A 8C D5 37 3E 97 66 1B A2 0D CF 89 E4 89

LSH-512-256("abc") = CD 89 23 10 53 26 02 33 2B 61 3F 1E C1 1A 69 62 FC A6 1E A0 9E CF FC D4 BC F7 58 58 D8 02 ED EC

LSH-512-384("abc") = 5F 34 4E FA A0 E4 3C CD 2E 5E 19 4D 60 39 79 4B 4F B4 31 F1 0F B4 B6 5F D4 5E 9D A4 EC DE 0F 27 B6 6E 8D BD FA 47 25 2E 0D 0B 74 1B FD 91 F9 FE

LSH-512-512("abc") = A3 D9 3C FE 60 DC 1A AC DD 3B D4 BE F0 A6 98 53 81 A3 96 C7 D4 9D 9F D1 77 79 56 97 C3 53 52 08 B5 C5 72 24 BE F2 10 84 D4 20 83 E9 5A 4B D8 EB 33 E8 69 81 2B 65 03 1C 42 88 19 A1 E7 CE 59 6D

التطبيقات

برنامج LSH مجاني للاستخدام العام أو الخاص، التجاري أو غير التجاري. يمكن تنزيل شفرة المصدر لتوزيع برنامج LSH المكتوب بلغات C وJava وPython من صفحة تفعيل استخدام التشفير التابعة لوكالة KISA. ^{[ 2 ]}

KCMVP

يُعدّ LSH أحد خوارزميات التشفير المعتمدة من قبل البرنامج الكوري للتحقق من صحة وحدات التشفير (KCMVP). ^{[ 3 ]}

التقييس

يتم تضمين LSH في المعيار التالي.

KS X 3262، دالة التجزئة LSH (باللغة الكورية) ^{[ 4 ]}

مراجع

1 2 3 4 5 6 كيم، دونغ تشان؛ هونغ، ديوكجو؛ لي، جونغ كيون؛ كيم، وو هوان؛ كوون، دايسونغ (2015). "LSH: عائلة جديدة من دوال التجزئة السريعة والآمنة" . أمن المعلومات وعلم التشفير - ICISC 2014. سلسلة محاضرات في علوم الحاسوب. المجلد 8949. دار نشر سبرينغر الدولية. الصفحات 286-313 . doi : 10.1007/978-3-319-15943-0_18 . ISBN 978-3-319-15943-0.
^ "KISA 암호이용활성화 - 암호알고리즘 소스코드" . Seed.kisa.or.kr .
^ "كيسا 암호이용활성화 - 개요" . Seed.kisa.or.kr .
↑ "المعايير والشهادات الكورية (باللغة الكورية)" .

[2] معالج Intel Core i7-4770K بسرعة 3.5 جيجاهرتز (Haswell)، نظام Ubuntu 12.04 64 بت، برنامج GCC 4.8.1 مع الخيار "-m64 -mavx2 -O3"

[3] معالج Intel Core i7-2600K بسرعة 3.40 جيجاهرتز (Sandy Bridge)، نظام Ubuntu 12.04 64 بت، برنامج GCC 4.8.1 مع الخيار "-m64 -msse4 -O3"

[4] معالج Intel Core 2 Quad Q9550 بسرعة 2.83 جيجاهرتز (يوركفيلد)، نظام التشغيل Windows 7 32 بت، برنامج Visual Studio 2012

[5] AMD FX-8350 @ 4GHz (Piledriver)، Ubuntu 12.04 64-bit، GCC 4.8.1 مع "-m64 -mxop -O3"

[6] معالج سامسونج Exynos 5250 ARM Cortex-A15 ثنائي النواة بسرعة 1.7 جيجاهرتز (Huins ACHRO 5250)، نظام أندرويد 4.1.1

[7] معالج كوالكوم سنابدراجون 800 كرايت 400 رباعي النواة بسرعة 2.26 جيجاهرتز (إل جي جي 2)، نظام أندرويد 4.4.2

[8] معالج كوالكوم سنابدراجون 800 كرايت 400 رباعي النواة بسرعة 2.3 جيجاهرتز (سامسونج جالاكسي إس 4)، نظام أندرويد 4.2.2

[9] معالج كوالكوم سنابدراجون 400 كرايت 300 ثنائي النواة بسرعة 1.7 جيجاهرتز (سامسونج جالاكسي إس 4 ميني)، نظام أندرويد 4.2.2

[KHL+14-1] 1 2 3 4 5 6 كيم، دونغ تشان؛ هونغ، ديوكجو؛ لي، جونغ كيون؛ كيم، وو هوان؛ كوون، دايسونغ (2015). "LSH: عائلة جديدة من دوال التجزئة السريعة والآمنة" . أمن المعلومات وعلم التشفير - ICISC 2014. سلسلة محاضرات في علوم الحاسوب. المجلد 8949. دار نشر سبرينغر الدولية. الصفحات 286-313 . doi : 10.1007/978-3-319-15943-0_18 . ISBN 978-3-319-15943-0.

[LSH_source-10] "KISA 암호이용활성화 - 암호알고리즘 소스코드" . Seed.kisa.or.kr .

[KCMVP-11] "كيسا 암호이용활성화 - 개요" . Seed.kisa.or.kr .

[KS_X_3262-12] "المعايير والشهادات الكورية (باللغة الكورية)" .

[ 1 ]

[ أ ]

[ ب ]

[ ج ]

[ د ]

[ e ]

[ f ]

[ g ]

[ h ]

[ 2 ]

[ 3 ]

[ 4 ]