В 1954 году, после начала национально-освободительной войны в Алжире, он одним из первых алжирских эмигрантов откликнулся на призыв ФНО и вступил в подпольную организацию на территории Франции. Вместе со своим другом Мохаммедом Зинет он занимался агитационной работой, информируя общественность о целях и позициях алжирского националистического движения. Под прикрытием мастер-классов для молодых актеров они организовывали встречи с алжирскими эмигрантами, отыскивая «потенциальный материал» для подрывной работы на вражеской территории. На одной из таких встреч Мохаммед Будиа познакомился со своей первой женой — француженкой алжирского происхождения Адриэ Герар, которая под оперативным псевдонимом Кемаль вошла в состав его диверсионной группы, созданной годом позже. Для Мохаммеда Будиа связь театра с политикой всегда была неразрывна. Одно не существовало без другого. Это было очевидно не только для единомышленников и соратников Будиа, но и для французских спецслужб, пытавшихся держать под контролем настроения и движения внутри алжирской диаспоры. В конечном итоге административные органы приняли решение о роспуске всех этих театральных компаний, небезосновательно заподозрив их в распространении революционно-сепаратистских идей.

К этому времени, в 1955 году, штаб ФНО ввел некоторые изменения в свою тактику, распространив военные действия на территорию метрополии путем диверсий и организаций актов саботажа на стратегически важных французских объектах. Эта задача была возложена на так называемых мусабили — вспомогательных бойцов алжирского сопротивления, действовавших нелегально во французских городах. Мохаммед Будиа стал командиром одной из наиболее успешных диверсионных групп специального назначения «Ла Спесиаль». Эта группа провела ряд громких диверсий на юге Франции, в том числе совершила нападение на логистический терминал «Мурепиан», расположенный в порту Марселя. В 1956 году во время одной из таких диверсионных вылазок Будиа был серьезно ранен в перестрелке с полицией. Он смог уйти от преследования, укрывшись на полулегальной квартире, из которой продолжил руководить диверсионным подпольем. Несколько лет французская полиция не могла выйти на след его группы, пока Мохаммед не допустил роковую ошибку, которая чуть не стоила ему головы. В 1958 году он принял участие в организации взрыва городского трубопровода Марселя и довольно быстро был схвачен полицией по горячим следам. За это и другие преступления Мохаммеду Будиа грозила гильотина, но суд вынес относительно мягкое решение, приговорив его к 20 годам тюремного заключения.

Его как особо опасного преступника периодически переводили из одной тюрьмы в другую. По мнению тюремных властей, эта мера должна была предотвратить попытку побега, помешать налаживанию связей с внешним миром, а также максимально осложнить адаптацию заключенного к новым условиям. В течение трех лет Будиа успел побывать в арестантском доме «Френ», «Ля Сантэ», тюрьмах «Анже» и «Бометт». С алжирскими сепаратистами тюремная администрация не особо церемонилась, но старалась держать их в отдельных камерах, чтобы избежать конфликтов с другими заключенными. К обычным уголовникам отношение было намного более терпимым. Делалось всё, чтобы сломать волю алжирцев. Со временем некоторые члены ФНО переставали интересоваться происходящим вокруг, постепенно превращаясь из опасных террористов в «овощи». Но Мохаммед Будиа был человеком совершенно иного склада. Он был не только талантливым театральным деятелем и баловнем парижской богемы, он с детства воспитал в себе качества жестокого бойца, способного выжить практически в самых невыносимых условиях. Тонкий ценитель французской кухни, завсегдатай дорогих ресторанов, любитель модных костюмов и столичных женщин — он легко сменил дорогой костюм на арестантскую робу и утренний кофе с круассанами на грубый черный хлеб и кус-кус. Даже находясь в одиночном заключении, он превратил бесконечность в своего союзника, использовав океан свободного времени с наибольшей для себя пользой, что помогло ему пережить постоянное физическое и психологическое давление. Мохаммед продолжал заниматься самообразованием и творчеством, насколько это позволяли тюремные условия. Сидя в одиночке, он перевел на алжирский диалект многие французские классические пьесы. В частности, адаптировал к родному языку пьесу Мольера «Мнимый больной». Там же, в «каменном мешке», Будиа написал получившие широкую известность пропагандистские театральные пьесы — «Роды» и «Оливковое дерево». В них он через диалоги героев в доходчивой форме старался донести даже до самого неискушенного зрителя необходимость и важность национально-освободительной борьбы. Насилие как ответ на любую форму несправедливости стало не только лейтмотивом всего творчества Будиа, но и его жизненной позицией. Вполне возможно, он вошел бы в историю не как изощренный террорист-убийца, а как выдающийся деятель антиколониального движения и талантливый театрал. Но маниакальная тяга к насилию, извращенное видение пути достижения социальной справедливости, а также врожденный или «привитый» авантюризм превращали и более достойных людей в банальных преступников — изгоев цивилизованного общества. Тюрьма «Бометт» стала для Мохаммеда Будиа непростым испытанием. Она считалась самой худшей тюрьмой не только во Франции, но и во всей Западной Европе. Антисанитария здесь царила страшная. Везде был мусор, насекомые и крысы в огромном количестве, к которым Мохаммед Будиа достаточно долго привыкал. Большинство заключенных составляли арабы, выходцы из Магриба. Как и на воле, в тюрьме они жили бандами, объединенными по этническому или территориальному принципу. Особенно много было корсиканцев, которые, считая себя коренными французами, держались обособленно. Попадались и представители неаполитанской каморры [114], жившие по своим законам, выглядевшие очень солидно, а потому другие заключенные старались не вступать с ними в конфликт. Часто возникали массовые потасовки, причем людей нередко избивали толпой. Охрана тюрьмы предпочитала не вмешиваться в происходящее. Заточки или ножи были практически у каждого арестанта. Как правило, их изготавливали из ложек или других металлических предметов, но попадались и искусно изготовленные керамические ножи. Гашиш в тюрьме был в свободном употреблении, как обычные сигареты. Администрация на это закрывала глаза — гашиш действовал как успокоительное и не доставлял особого беспокойства. Камера представляла собой небольшое помещение с решеткой вместо внутренней стены, выходящей в коридор, которую не разрешалось завешивать. Трехъярусная кровать, стол, иногда холодильник. Кормили два раза в день, для тюремных условий довольно сносно — кус-кус, рис, иногда давали мясо в виде рагу.

Каждую тюрьму, которую ему пришлось посетить, Мохаммед Будиа превращал в свою творческую мастерскую, каждую камеру — в рабочий кабинет. В тюрьме «Бометт» с разрешения администрации он поставил пьесу «Роды». Желая себя хоть чем-то занять и убить время, в «театральном эксперименте» приняли участие практически все арестанты тюремного блока. Одни заключенные заучивали роли и играли на импровизированной сцене, другие занимались изготовлением костюмов и декораций. По словам самого Будиа, делясь своей страстью к театру, он смог не только вывести заключенных из глубокой депрессии, но и заинтересовать многих уголовников леворадикальными социальными идеями.