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