23101654152

Committed 15 Mar 2026 02:32AM UTC coverage: 89.741% (+0.008%) from 89.733%

Build # 23101654152

Build Type

Pull #5443

github

Committed by

web-flow

Commit Message

Merge 065853244 into 6d28178fb

Pull Request Pull Request #5443: Add AVX2 implementation of IDEA

Coverage Stats

104350 of 116279 relevant lines covered (89.74%)

11425914.69 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

95.49

/src/lib/block/idea/idea.cpp

/*
* IDEA
* (C) 1999-2010,2015 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/internal/idea.h>

#include <botan/internal/ct_utils.h>
#include <botan/internal/loadstor.h>

#if defined(BOTAN_HAS_CPUID)
   #include <botan/internal/cpuid.h>
#endif

namespace Botan {

namespace {

/*
* Multiplication modulo 65537
*/
inline uint16_t mul(uint16_t x, uint16_t y) {
   const uint32_t P = static_cast<uint32_t>(x) * y;
   const auto P_mask = CT::Mask<uint16_t>(CT::Mask<uint32_t>::is_zero(P));

   const uint32_t P_hi = P >> 16;
   const uint32_t P_lo = P & 0xFFFF;

   const uint16_t carry = static_cast<uint16_t>(P_lo < P_hi);
   const uint16_t r_1 = static_cast<uint16_t>((P_lo - P_hi) + carry);
   const uint16_t r_2 = 1 - x - y;

   return P_mask.select(r_2, r_1);
}

/*
* Find multiplicative inverses modulo 65537
*
* 65537 is prime; thus Fermat's little theorem tells us that
* x^65537 == x modulo 65537, which means
* x^(65537-2) == x^-1 modulo 65537 since
* x^(65537-2) * x == 1 mod 65537
*
* Do the exponentiation with a basic square and multiply: all bits are
* of exponent are 1 so we always multiply
*/
uint16_t mul_inv(uint16_t x) {
   uint16_t y = x;

   for(size_t i = 0; i != 15; ++i) {
      y = mul(y, y);  // square
      y = mul(y, x);
   }

   return y;
}

/**
* IDEA is involutional, depending only on the key schedule
*/
void idea_op(const uint8_t in[], uint8_t out[], size_t blocks, const uint16_t K[52]) {
   const size_t BLOCK_SIZE = 8;

   CT::poison(in, blocks * 8);
   CT::poison(out, blocks * 8);
   CT::poison(K, 52);

   for(size_t i = 0; i < blocks; ++i) {
      uint16_t X1 = 0;
      uint16_t X2 = 0;
      uint16_t X3 = 0;
      uint16_t X4 = 0;
      load_be(in + BLOCK_SIZE * i, X1, X2, X3, X4);

      for(size_t j = 0; j != 8; ++j) {
         X1 = mul(X1, K[6 * j + 0]);
         X2 += K[6 * j + 1];
         X3 += K[6 * j + 2];
         X4 = mul(X4, K[6 * j + 3]);

         const uint16_t T0 = X3;
         X3 = mul(X3 ^ X1, K[6 * j + 4]);

         const uint16_t T1 = X2;
         X2 = mul((X2 ^ X4) + X3, K[6 * j + 5]);
         X3 += X2;

         X1 ^= X2;
         X4 ^= X3;
         X2 ^= T0;
         X3 ^= T1;
      }

      X1 = mul(X1, K[48]);
      X2 += K[50];
      X3 += K[49];
      X4 = mul(X4, K[51]);

      store_be(out + BLOCK_SIZE * i, X1, X3, X2, X4);
   }

   CT::unpoison(in, blocks * 8);
   CT::unpoison(out, blocks * 8);
   CT::unpoison(K, 52);
}

}  // namespace

size_t IDEA::parallelism() const {
#if defined(BOTAN_HAS_IDEA_AVX2)
   if(CPUID::has(CPUID::Feature::AVX2)) {
      return 16;
   }
#endif

#if defined(BOTAN_HAS_IDEA_SSE2)
   if(CPUID::has(CPUID::Feature::SSE2)) {
      return 8;
   }
#endif

   return 1;
}

std::string IDEA::provider() const {
#if defined(BOTAN_HAS_IDEA_AVX2)
   if(auto feat = CPUID::check(CPUID::Feature::AVX2)) {
      return *feat;
   }
#endif

#if defined(BOTAN_HAS_IDEA_SSE2)
   if(auto feat = CPUID::check(CPUID::Feature::SSE2)) {
      return *feat;
   }
#endif

   return "base";
}

/*
* IDEA Encryption
*/
void IDEA::encrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const {
   assert_key_material_set();

#if defined(BOTAN_HAS_IDEA_AVX2)
   if(CPUID::has(CPUID::Feature::AVX2)) {
      while(blocks >= 16) {
         avx2_idea_op_16(in, out, m_EK.data());
         in += 16 * BLOCK_SIZE;
         out += 16 * BLOCK_SIZE;
         blocks -= 16;
      }
   }
#endif

#if defined(BOTAN_HAS_IDEA_SSE2)
   if(CPUID::has(CPUID::Feature::SSE2)) {
      while(blocks >= 8) {
         sse2_idea_op_8(in, out, m_EK.data());
         in += 8 * BLOCK_SIZE;
         out += 8 * BLOCK_SIZE;
         blocks -= 8;
      }
   }
#endif

   idea_op(in, out, blocks, m_EK.data());
}

/*
* IDEA Decryption
*/
void IDEA::decrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const {
   assert_key_material_set();

#if defined(BOTAN_HAS_IDEA_AVX2)
   if(CPUID::has(CPUID::Feature::AVX2)) {
      while(blocks >= 16) {
         avx2_idea_op_16(in, out, m_DK.data());
         in += 16 * BLOCK_SIZE;
         out += 16 * BLOCK_SIZE;
         blocks -= 16;
      }
   }
#endif

#if defined(BOTAN_HAS_IDEA_SSE2)
   if(CPUID::has(CPUID::Feature::SSE2)) {
      while(blocks >= 8) {
         sse2_idea_op_8(in, out, m_DK.data());
         in += 8 * BLOCK_SIZE;
         out += 8 * BLOCK_SIZE;
         blocks -= 8;
      }
   }
#endif

   idea_op(in, out, blocks, m_DK.data());
}

bool IDEA::has_keying_material() const {
   return !m_EK.empty();
}

/*
* IDEA Key Schedule
*/
void IDEA::key_schedule(std::span<const uint8_t> key) {
   m_EK.resize(52);
   m_DK.resize(52);

   CT::poison(key.data(), 16);
   CT::poison(m_EK.data(), 52);
   CT::poison(m_DK.data(), 52);

   secure_vector<uint64_t> K(2);

   K[0] = load_be<uint64_t>(key.data(), 0);
   K[1] = load_be<uint64_t>(key.data(), 1);

   for(size_t off = 0; off != 48; off += 8) {
      for(size_t i = 0; i != 8; ++i) {
         m_EK[off + i] = static_cast<uint16_t>(K[i / 4] >> (48 - 16 * (i % 4)));
      }

      const uint64_t Kx = (K[0] >> 39);
      const uint64_t Ky = (K[1] >> 39);

      K[0] = (K[0] << 25) | Ky;
      K[1] = (K[1] << 25) | Kx;
   }

   for(size_t i = 0; i != 4; ++i) {
      m_EK[48 + i] = static_cast<uint16_t>(K[i / 4] >> (48 - 16 * (i % 4)));
   }

   m_DK[0] = mul_inv(m_EK[48]);
   m_DK[1] = -m_EK[49];
   m_DK[2] = -m_EK[50];
   m_DK[3] = mul_inv(m_EK[51]);

   for(size_t i = 0; i != 8 * 6; i += 6) {
      m_DK[i + 4] = m_EK[46 - i];
      m_DK[i + 5] = m_EK[47 - i];
      m_DK[i + 6] = mul_inv(m_EK[42 - i]);
      m_DK[i + 7] = -m_EK[44 - i];
      m_DK[i + 8] = -m_EK[43 - i];
      m_DK[i + 9] = mul_inv(m_EK[45 - i]);
   }

   std::swap(m_DK[49], m_DK[50]);

   CT::unpoison(key.data(), 16);
   CT::unpoison(m_EK.data(), 52);
   CT::unpoison(m_DK.data(), 52);
}

void IDEA::clear() {
   zap(m_EK);
   zap(m_DK);
}

}  // namespace Botan

1	/*
2	* IDEA
3	* (C) 1999-2010,2015 Jack Lloyd
4	*
5	* Botan is released under the Simplified BSD License (see license.txt)
6	*/
7
8	#include <botan/internal/idea.h>
9
10	#include <botan/internal/ct_utils.h>
11	#include <botan/internal/loadstor.h>
12
13	#if defined(BOTAN_HAS_CPUID)
14	#include <botan/internal/cpuid.h>
15	#endif
16
17	namespace Botan {
18
19	namespace {
20
21	/*
22	* Multiplication modulo 65537
23	*/
24	inline uint16_t mul(uint16_t x, uint16_t y) {	1,959,804✔
25	const uint32_t P = static_cast<uint32_t>(x) * y;	1,959,804✔
26	const auto P_mask = CT::Mask<uint16_t>(CT::Mask<uint32_t>::is_zero(P));	1,959,804✔
27
28	const uint32_t P_hi = P >> 16;	1,959,804✔
29	const uint32_t P_lo = P & 0xFFFF;	1,959,804✔
30
31	const uint16_t carry = static_cast<uint16_t>(P_lo < P_hi);	1,959,804✔
32	const uint16_t r_1 = static_cast<uint16_t>((P_lo - P_hi) + carry);	1,959,804✔
33	const uint16_t r_2 = 1 - x - y;	1,959,804✔
34
35	return P_mask.select(r_2, r_1);	1,959,804✔
36	}
37
38	/*
39	* Find multiplicative inverses modulo 65537
40	*
41	* 65537 is prime; thus Fermat's little theorem tells us that
42	* x^65537 == x modulo 65537, which means
43	* x^(65537-2) == x^-1 modulo 65537 since
44	* x^(65537-2) * x == 1 mod 65537
45	*
46	* Do the exponentiation with a basic square and multiply: all bits are
47	* of exponent are 1 so we always multiply
48	*/
49	uint16_t mul_inv(uint16_t x) {	58,554✔
50	uint16_t y = x;	58,554✔
51
52	for(size_t i = 0; i != 15; ++i) {	936,864✔
53	y = mul(y, y); // square	878,310✔
54	y = mul(y, x);	878,310✔
55	}
56
57	return y;	58,554✔
58	}
59
60	/**
61	* IDEA is involutional, depending only on the key schedule
62	*/
63	void idea_op(const uint8_t in[], uint8_t out[], size_t blocks, const uint16_t K[52]) {	5,932✔
64	const size_t BLOCK_SIZE = 8;	5,932✔
65
66	CT::poison(in, blocks * 8);	5,932✔
67	CT::poison(out, blocks * 8);	5,932✔
68	CT::poison(K, 52);	5,932✔
69
70	for(size_t i = 0; i < blocks; ++i) {	11,908✔
71	uint16_t X1 = 0;	5,976✔
72	uint16_t X2 = 0;	5,976✔
73	uint16_t X3 = 0;	5,976✔
74	uint16_t X4 = 0;	5,976✔
75	load_be(in + BLOCK_SIZE * i, X1, X2, X3, X4);	5,976✔
76
77	for(size_t j = 0; j != 8; ++j) {	53,784✔
78	X1 = mul(X1, K[6 * j + 0]);	47,808✔
79	X2 += K[6 * j + 1];	47,808✔
80	X3 += K[6 * j + 2];	47,808✔
81	X4 = mul(X4, K[6 * j + 3]);	47,808✔
82
83	const uint16_t T0 = X3;	47,808✔
84	X3 = mul(X3 ^ X1, K[6 * j + 4]);	47,808✔
85
86	const uint16_t T1 = X2;	47,808✔
87	X2 = mul((X2 ^ X4) + X3, K[6 * j + 5]);	47,808✔
88	X3 += X2;	47,808✔
89
90	X1 ^= X2;	47,808✔
91	X4 ^= X3;	47,808✔
92	X2 ^= T0;	47,808✔
93	X3 ^= T1;	47,808✔
94	}
95
96	X1 = mul(X1, K[48]);	5,976✔
97	X2 += K[50];	5,976✔
98	X3 += K[49];	5,976✔
99	X4 = mul(X4, K[51]);	5,976✔
100
101	store_be(out + BLOCK_SIZE * i, X1, X3, X2, X4);	5,976✔
102	}
103
104	CT::unpoison(in, blocks * 8);	5,932✔
105	CT::unpoison(out, blocks * 8);	5,932✔
106	CT::unpoison(K, 52);	5,932✔
107	}	5,932✔
108
109	} // namespace
110
111	size_t IDEA::parallelism() const {	3,253✔
112	#if defined(BOTAN_HAS_IDEA_AVX2)
113	if(CPUID::has(CPUID::Feature::AVX2)) {	3,253✔
114	return 16;
115	}
116	#endif
117
118	#if defined(BOTAN_HAS_IDEA_SSE2)
119	if(CPUID::has(CPUID::Feature::SSE2)) {	×
120	return 8;	×
121	}
122	#endif
123
124	return 1;
125	}
126
127	std::string IDEA::provider() const {	1,084✔
128	#if defined(BOTAN_HAS_IDEA_AVX2)
129	if(auto feat = CPUID::check(CPUID::Feature::AVX2)) {	1,084✔
130	return *feat;	2,168✔
131	}	1,084✔
132	#endif
133
134	#if defined(BOTAN_HAS_IDEA_SSE2)
135	if(auto feat = CPUID::check(CPUID::Feature::SSE2)) {	×
136	return *feat;	×
137	}	×
138	#endif
139
140	return "base";	×
141	}
142
143	/*
144	* IDEA Encryption
145	*/
146	void IDEA::encrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const {	5,676✔
147	assert_key_material_set();	5,676✔
148
149	#if defined(BOTAN_HAS_IDEA_AVX2)
150	if(CPUID::has(CPUID::Feature::AVX2)) {	3,508✔
151	while(blocks >= 16) {	3,563✔
152	avx2_idea_op_16(in, out, m_EK.data());	55✔
153	in += 16 * BLOCK_SIZE;	55✔
154	out += 16 * BLOCK_SIZE;	55✔
155	blocks -= 16;	55✔
156	}
157	}
158	#endif
159
160	#if defined(BOTAN_HAS_IDEA_SSE2)
161	if(CPUID::has(CPUID::Feature::SSE2)) {	3,508✔
162	while(blocks >= 8) {	1,887✔
163	sse2_idea_op_8(in, out, m_EK.data());	5✔
164	in += 8 * BLOCK_SIZE;	5✔
165	out += 8 * BLOCK_SIZE;	5✔
166	blocks -= 8;	5✔
167	}
168	}
169	#endif
170
171	idea_op(in, out, blocks, m_EK.data());	3,508✔
172	}	3,508✔
173
174	/*
175	* IDEA Decryption
176	*/
177	void IDEA::decrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const {	4,592✔
178	assert_key_material_set();	4,592✔
179
180	#if defined(BOTAN_HAS_IDEA_AVX2)
181	if(CPUID::has(CPUID::Feature::AVX2)) {	2,424✔
182	while(blocks >= 16) {	2,479✔
183	avx2_idea_op_16(in, out, m_DK.data());	55✔
184	in += 16 * BLOCK_SIZE;	55✔
185	out += 16 * BLOCK_SIZE;	55✔
186	blocks -= 16;	55✔
187	}
188	}
189	#endif
190
191	#if defined(BOTAN_HAS_IDEA_SSE2)
192	if(CPUID::has(CPUID::Feature::SSE2)) {	2,424✔
193	while(blocks >= 8) {	1,345✔
194	sse2_idea_op_8(in, out, m_DK.data());	5✔
195	in += 8 * BLOCK_SIZE;	5✔
196	out += 8 * BLOCK_SIZE;	5✔
197	blocks -= 8;	5✔
198	}
199	}
200	#endif
201
202	idea_op(in, out, blocks, m_DK.data());	2,424✔
203	}	2,424✔
204
205	bool IDEA::has_keying_material() const {	14,604✔
206	return !m_EK.empty();	14,604✔
207	}
208
209	/*
210	* IDEA Key Schedule
211	*/
212	void IDEA::key_schedule(std::span<const uint8_t> key) {	3,253✔
213	m_EK.resize(52);	3,253✔
214	m_DK.resize(52);	3,253✔
215
216	CT::poison(key.data(), 16);	3,253✔
217	CT::poison(m_EK.data(), 52);	3,253✔
218	CT::poison(m_DK.data(), 52);	3,253✔
219
220	secure_vector<uint64_t> K(2);	3,253✔
221
222	K[0] = load_be<uint64_t>(key.data(), 0);	3,253✔
223	K[1] = load_be<uint64_t>(key.data(), 1);	3,253✔
224
225	for(size_t off = 0; off != 48; off += 8) {	22,771✔
226	for(size_t i = 0; i != 8; ++i) {	175,662✔
227	m_EK[off + i] = static_cast<uint16_t>(K[i / 4] >> (48 - 16 * (i % 4)));	156,144✔
228	}
229
230	const uint64_t Kx = (K[0] >> 39);	19,518✔
231	const uint64_t Ky = (K[1] >> 39);	19,518✔
232
233	K[0] = (K[0] << 25) \| Ky;	19,518✔
234	K[1] = (K[1] << 25) \| Kx;	19,518✔
235	}
236
237	for(size_t i = 0; i != 4; ++i) {	16,265✔
238	m_EK[48 + i] = static_cast<uint16_t>(K[i / 4] >> (48 - 16 * (i % 4)));	13,012✔
239	}
240
241	m_DK[0] = mul_inv(m_EK[48]);	3,253✔
242	m_DK[1] = -m_EK[49];	3,253✔
243	m_DK[2] = -m_EK[50];	3,253✔
244	m_DK[3] = mul_inv(m_EK[51]);	3,253✔
245
246	for(size_t i = 0; i != 8 * 6; i += 6) {	29,277✔
247	m_DK[i + 4] = m_EK[46 - i];	26,024✔
248	m_DK[i + 5] = m_EK[47 - i];	26,024✔
249	m_DK[i + 6] = mul_inv(m_EK[42 - i]);	26,024✔
250	m_DK[i + 7] = -m_EK[44 - i];	26,024✔
251	m_DK[i + 8] = -m_EK[43 - i];	26,024✔
252	m_DK[i + 9] = mul_inv(m_EK[45 - i]);	26,024✔
253	}
254
255	std::swap(m_DK[49], m_DK[50]);	3,253✔
256
257	CT::unpoison(key.data(), 16);	3,253✔
258	CT::unpoison(m_EK.data(), 52);	3,253✔
259	CT::unpoison(m_DK.data(), 52);	3,253✔
260	}	3,253✔
261
262	void IDEA::clear() {	2,168✔
263	zap(m_EK);	2,168✔
264	zap(m_DK);	2,168✔
265	}	2,168✔
266
267	} // namespace Botan

randombit / botan / 23101654152

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous